java 实现迷宫回溯算法示例详解

用一个7 x 7的矩形表示迷宫，0和1分别表示的是通路和障碍。通过设计编写程序找到蓝色小球达到蓝色旗子的路线

思路：

构建一个迷宫（用二维数组）实现找通路的方法findRoad()
构建二维数组不难，我们主要是要实现findRoad()这个方法，在实现这个方法前，我们需要约定好一下几个点：小球的位置当作入口（1，1），小旗的位置当作出口（5，5）数组里数的含义分别为(0没有走过)、(1障碍)、(2走过且为正确的路线)、(3走过且为错误的路线)将我们每一步的走法称为策略：下 -> 右 -> 上 ->左

实现

首先构建出迷宫

public static void main(String[] args) {
    //1.创建二维数组模拟迷宫
    int[][] maze = new int[7][7];
    //2.初始化迷宫
    for (int i = 0; i < maze.length; i++) {
      //maze[i][j]:i控制行 j:控制列
      maze[0][i] = 1;//第1行都为1
      maze[6][i] = 1;//最后一行都为1
      maze[i][0] = 1;//第一列都为1
      maze[i][6] = 1;//最后一列都为1
      //其他位置的1
      maze[4][1] = 1;
      maze[4][2] = 1;
      maze[4][3] = 1;
      maze[4][4] = 1;
      maze[3][4] = 1;
      maze[2][3] = 1;
    }
    //打印迷宫
    System.out.println("完成迷宫初始化：");
    for (int i = 0; i < maze.length; i++) {
      for (int j = 0; j < maze[i].length; j++) {
        System.out.print(maze[i][j] + " ");
      }
      System.out.println();
    }
  }

然后写findRoad()方法

   * 使用递归回溯找通路  （5，5为出口）
   * @param maze 迷宫
   * @param i  从哪个位置开始找
   * @param j  从哪个位置开始找
   * @return 找到通路返回true 否则false
   */
  public static boolean findRoad(int[][] maze, int i, int j) {
    //策略：下 -> 右 -> 上 ->左
    //0：没有走过 1：障碍 2:走过且为正确的路线 3：走过且为错误的路线
    if (maze[5][5] == 2) {//找到通路
      return true;
    } else {
      if (maze[i][j] == 0) {
        //当前点没走过，按策略走
        maze[i][j] = 2;//当前点改为2，假定能走通
        if (findRoad(maze, i + 1, j)) {//向下走
          return true;
        } else if (findRoad(maze, i, j + 1)) {//向右走
          return true;
        } else if (findRoad(maze, i - 1, j)) {//向上走
          return true;
        } else if (findRoad(maze, i, j - 1)) {//向左走
          return true;
        } else {
          //该点无法走通
          maze[i][j] = 3;
          return false;//返回到上个方法（即返回到上个点）
        }
      } else {
        //该点为 1或2或3，无法走通，直接返回上个方法（即上个点）
        return false;
      }
    }
  }

main方法调用findRoad()方法，传入创建好的迷宫，和入口点（1，1）

//mian方法中调用findRoad()方法
    findRoad(maze,1,1);
    //打印迷宫
    System.out.println("完成路线的迷宫：");
    for (int i = 0; i < maze.length; i++) {
      for (int j = 0; j < maze[i].length; j++) {
        System.out.print(maze[i][j] + " ");
      }
      System.out.println();
    }

效果

到此这篇关于java 实现迷宫回溯算法示例详解的文章就介绍到这了,更多相关java 实现迷宫回溯算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！