专栏首页SpringCloud专栏回溯算法解迷宫问题(java版)

回溯算法解迷宫问题(java版)

    以一个M×N的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计程序,对任意设定的迷宫,求出从入口到出口的所有通路。

    下面我们来详细讲一下迷宫问题的回溯算法。

    该图是一个迷宫的图。1代表是墙不能走,0是可以走的路线。只能往上下左右走,直到从左上角到右下角出口。

    做法是用一个二维数组来定义迷宫的初始状态,然后从左上角开始,不停的去试探所有可行的路线,碰到1就结束本次路径,然后探索其他的方向,当然我们要标记一下已经走的路线,不能反复的在两个可行的格子之间来回走。直到走到出口为止,算找到了一个正确路径。

    程序如下,具体做法看注释即可。

package huisu;

/**
 * Created by wolf on 2016/3/21.
 */
public class MiGong {
    /**
     * 定义迷宫数组
     */
    private int[][] array = {
            {0, 0, 1, 0, 0, 0, 1, 0},
            {0, 0, 1, 0, 0, 0, 1, 0},
            {0, 0, 1, 0, 1, 1, 0, 1},
            {0, 1, 1, 1, 0, 0, 1, 0},
            {0, 0, 0, 1, 0, 0, 0, 0},
            {0, 1, 0, 0, 0, 1, 0, 1},
            {0, 1, 1, 1, 1, 0, 0, 1},
            {1, 1, 0, 0, 0, 1, 0, 1},
            {1, 1, 0, 0, 0, 0, 0, 0}

    };
    private int maxLine = 8;
    private int maxRow = 9;

    public static void main(String[] args) {
        System.out.println(System.currentTimeMillis());
        new MiGong().check(0, 0);
        System.out.println(System.currentTimeMillis());
    }

    private void check(int i, int j) {
        //如果到达右下角出口
        if (i == maxRow - 1 && j == maxLine - 1) {
            print();
            return;
        }

        //向右走
        if (canMove(i, j, i, j + 1)) {
            array[i][j] = 5;
            check(i, j + 1);
            array[i][j] = 0;
        }
        //向左走
        if (canMove(i, j, i, j - 1)) {
            array[i][j] = 5;
            check(i, j - 1);
            array[i][j] = 0;
        }
        //向下走
        if (canMove(i, j, i + 1, j)) {
            array[i][j] = 5;
            check(i + 1, j);
            array[i][j] = 0;
        }
        //向上走
        if (canMove(i, j, i - 1, j)) {
            array[i][j] = 5;
            check(i - 1, j);
            array[i][j] = 0;
        }
    }

    private boolean canMove(int i, int j, int targetI, int targetJ) {
//        System.out.println("从第" + (i + 1) + "行第" + (j + 1) + "列,走到第" + (targetI + 1) + "行第" + (targetJ + 1) + "列");
        if (targetI < 0 || targetJ < 0 || targetI >= maxRow || targetJ >= maxLine) {
//            System.out.println("到达最左边或最右边,失败了");
            return false;
        }
        if (array[targetI][targetJ] == 1) {
//            System.out.println("目标是墙,失败了");
            return false;
        }
        //避免在两个空格间来回走
        if (array[targetI][targetJ] == 5) {
//            System.out.println("来回走,失败了");
            return false;
        }

        return true;
    }

    private void print() {
        System.out.println("得到一个解:");
        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxLine; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
}

    我把打印每一步路径判断的地方注释掉了,放开注释就能看到所有走的路径。     程序执行效率是非常快,基本上是在3ms之内得到所有路径。

    原本只看图时我还以为只有3条路径,没想到程序打出来了8条。后来仔细看看,果然是有8条路径……

    打印结果如下,5是用来标记路径的:

1458551044499
得到一个解:
5 5 1 0 0 0 1 0 
5 5 1 0 0 0 1 0 
5 0 1 0 1 1 0 1 
5 1 1 1 0 0 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
得到一个解:
5 5 1 0 0 0 1 0 
5 5 1 0 0 0 1 0 
5 0 1 0 1 1 0 1 
5 1 1 1 5 5 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
得到一个解:
5 5 1 0 0 0 1 0 
0 5 1 0 0 0 1 0 
5 5 1 0 1 1 0 1 
5 1 1 1 0 0 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
得到一个解:
5 5 1 0 0 0 1 0 
0 5 1 0 0 0 1 0 
5 5 1 0 1 1 0 1 
5 1 1 1 5 5 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
得到一个解:
5 0 1 0 0 0 1 0 
5 5 1 0 0 0 1 0 
5 5 1 0 1 1 0 1 
5 1 1 1 0 0 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
得到一个解:
5 0 1 0 0 0 1 0 
5 5 1 0 0 0 1 0 
5 5 1 0 1 1 0 1 
5 1 1 1 5 5 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
得到一个解:
5 0 1 0 0 0 1 0 
5 0 1 0 0 0 1 0 
5 0 1 0 1 1 0 1 
5 1 1 1 0 0 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
得到一个解:
5 0 1 0 0 0 1 0 
5 0 1 0 0 0 1 0 
5 0 1 0 1 1 0 1 
5 1 1 1 5 5 1 0 
5 5 5 1 5 5 5 0 
0 1 5 5 5 1 5 1 
0 1 1 1 1 0 5 1 
1 1 0 0 0 1 5 1 
1 1 0 0 0 0 5 0 
1458551044503

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java简单实现滑动窗口

    由于最近有一个统计单位时间内某key的访问次数的需求,譬如每5秒访问了redis的某key超过100次,就取出该key单独处理。

    天涯泪小武
  • 4 Springboot中使用redis存储集合数据,并模拟条件查询、分页读取

    前面几篇讲了使用redis存储单个对象,自动缓存、更新、删除的做法,在实际项目中,更常用的是分页查询集合数据,条件查询(譬如按照添加时间倒序排列)。

    天涯泪小武
  • android自定义adapter之简单写法

        自定义adapter比较常用,很多人还在使用extends BaseAdapter,然后写一大堆重复的代码,这里是提供一个封装的工具类,把重复的代码都省...

    天涯泪小武
  • java概念1

    public static void main(String[] args) {//其中[]也可以写在args后面,args也可以随便写成其他字母,例如asd...

    闵开慧
  • 优化 Java 中的多态代码

    Oracle的Java是一个门快速的语言,有时候它可以和C++一样快。编写Java代码时,我们通常使用接口、继承或者包装类(wrapper class)来实现多...

    用户1257393
  • Java中多个ifelse语句的替代设计

    ifelse是任何编程语言的重要组成部分。但是我们编写了大量嵌套的if语句,这使得我们的代码更加复杂和难以维护。

    王知无
  • 历届试题 小朋友排队

    问题描述   n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列,但是每次只能交换位置相邻的两个小朋友。

    AI那点小事
  • 线性查找

      线性查找也叫顺序查找,这是最基本的一种查找方法,从给定的值中进行搜索,从一端开始逐一检查每个元素,直到找到所需元素的过程。   如果元素个数为 N,那么线性...

    IT可乐
  • C++-面向对象(五)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • JAVA之学习system类的概述和成员方法

    吾爱乐享

扫码关注云+社区

领取腾讯云代金券