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

怼烎@ 2023-07-10 14:04 3阅读 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);
    }

![在这里插入图片描述][20200302205947794.png]

[20200302205947794.png]: https://img-blog.csdnimg.cn/20200302205947794.png