算法_递归_回溯_迷宫问题-蒲公英云

算法_递归_回溯_迷宫问题

怼烎@ 2023-07-10 14:04 74阅读 0赞

文章目录

- 问题描述
- 准备工作
- - 绘制迷宫
  - 打印迷宫
- 走迷宫
- 测试

问题描述

判断一个迷宫是否可以走通。
注意：非求最优解，仅通过回溯判断是否有解

准备工作

绘制迷宫

/**
 * 绘制地图
 * @param maze
 */
private static void paintMaze(int[][] maze) {
    //1表示墙
    for (int i = 0; i < 10; i++) {
        maze[0][i] = 1;
        maze[9][i] = 1;
        maze[i][0] = 1;
        maze[i][9] = 1;
    }
    //随机设置障碍
    Random random = new Random();
    for (int i = 0; i < 20; i++) {
        maze[random.nextInt(9)][random.nextInt(9)] = 1;
    }
    //起点1,1 终点8,8 确保为0
    maze[1][1] = 0;
    maze[8][8] = 0;
}

打印迷宫

/**
 * 打印迷宫
 * @param maze
 */
private static void print(int[][] maze) {
    for (int[] arr : maze) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

走迷宫

/**
 * 递归回溯走迷宫
 * 策略 右→下→左→上
 * 1：墙
 * 2：可行
 * 3：死路
 * @param maze
 * @param i    当前横坐标
 * @param j    当前纵坐标
 * @return
 */
private static boolean go(int[][] maze, int i, int j) {
    if (maze[8][8] == 2) {
        return true;
    }
    if (maze[i][j] == 0) {
        maze[i][j] = 2;
        // 右→下→左→上
        if (go(maze, i, j + 1) || go(maze, i - 1, j) || go(maze, i, j - 1) || go(maze, i + 1, j)) {
            return true;
        }
        maze[i][j] = 3;
    }
    return false;
}

测试

public static void main(String[] args) {
    //二维数据模拟迷宫
    int[][] maze = new int[10][10];
    paintMaze(maze);
    print(maze);
    System.out.println(go(maze, 1, 1));
    print(maze);
}