经典算法（20）给女朋友讲明白迷宫问题

川长思鸟来 2023-07-10 11:28 9阅读 0赞

> **写在前面**： 我是 「扬帆向海」，这个昵称来源于我的名字以及女朋友的名字。我热爱技术、热爱开源、热爱编程。`技术是开源的、知识是共享的`。  
>   
> 这博客是对自己学习的一点点总结及记录，如果您对 *Java*、*算法* 感兴趣，可以关注我的动态，我们一起学习。  
>   
> `用知识改变命运，让我们的家人过上更好的生活`。

***相关文章***

[点此查看 【算法系列】 博客文章][Link 1]

--------------------

### 文章目录 ###

*   *   *  1、问题描述
         *  2、实现逻辑
         *  3、代码实现

### 1、问题描述 ###

***今天女朋友在刷算法题，委屈巴巴的问我迷宫问题如何解决**？*

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70]  
***先看一下问题的描述***：

> 有一个迷宫地图，其中设置了障碍物，四周还有墙壁。只能横着走或竖着走，不能斜着走。从一个位置走到下一个位置只能通过向上（或者向右、或者向下、或者向左）的策略来实现。一个人从起点出发，如何找到一条到达终点的通路？

看完问题描述，我就大概画了一个迷宫图，如下图所示：

***迷宫图示***：  
![在这里插入图片描述][20200228164652287.png]

### 2、实现逻辑 ###

***我让她看这个图，然后思考如何实现？***

**她**：“用二维数组？”

**我**：“对的！在这个算法中，使用二维矩阵来模拟迷宫地图”

**我**：“迷宫中的通路和墙壁如何表示？”

**她**：“可以使用0和1表示”

**我**：“对，很聪明！`1` 代表该位置不能到达（如墙壁或者遮挡物），`0` 代表该位置可以到达。”

**我**：“比如小明在迷宫中寻找通路的时候，有没有重复走的情况。如果重复走，如何避免这个情况？”

**她**：“每当走过一个位置就将迷宫地图的对应位置做一个标记，以免重复走，一步步的寻找通路最终到达终点位置。”

到这里，看来她也明白了好多！很开心

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 1]  
**我**：“从每一个位置出发，在走下一步的时候都可以有几种选择？”

**她**：“从每一个位置出发，在走下一步的时候都有四种选择（向上走、向右走、向下走、向左走）。”

***然后我就分析了如何走的算法逻辑***

*  先选择一个方向开始走，如果该方向能够走下去，那么就往这个方向开始走，当前位置切换为下一个位置。
 *  如果这个方向不能走，那么换个方向开始走。
 *  如果所有方向都走不通，那么退出当前位置，到上一步的位置去，当前位置切换为上一步的位置。
 *  一直这样执行下去，如果当前位置是终点，那么结束。如果走过了所有的路径都没能到达终点，那么说明这个迷宫走不出来。

**我**：“现在明白没？”

**她**：“明白了！”

**我**：“那你想想如何实现这个算法？”

**她**：使用 ***`递归的方式求解`***

**我**：“还有其它方式没？ ***`广度优先遍历`*** 和 ***`深度优先遍历`*** 会不会？”

**她：**“不会！”

**我**：“嗯嗯，那你就用递归的方式实现吧！首先制定 在迷宫中寻找出路的策略依次是：***向上走、向右走、向下走、向左走***”

--------------------

***接下来就开始写代码吧***！

### 3、代码实现 ###

**我**：“你先用二维矩阵画出迷宫地图，包括挡板的位置”

她噼里啪啦一顿操作就写完了

public class Maze { 
    
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
    
            int i; // 横坐标
            int j; // 纵坐标
    
            // 创建一个10×10的地图
            int[][] map = new int[10][10];
    
            // 设置左、右两边为墙，用“1”来代替墙面
            for (i = 0; i < 10; i++) { 
                map[i][0] = 1;
                map[i][9] = 1;
            }
    
            // 设置上、下两边为墙，用“1”来代替墙面
            for (i = 0; i < 10; i++) { 
                map[0][i] = 1;
                map[9][i] = 1;
            }
    
            // 设置挡板位置
            map[4][1] = 1;
            map[4][2] = 1;
            map[4][3] = 1;
    
            System.out.println("迷宫地图的情况：");
            for (i = 0; i < 10; i++) { 
                for (j = 0; j < 10; j++) { 
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

***迷宫地图的情况：***  
![在这里插入图片描述][20200302125658983.png]

--------------------

**我**：“现在你可以写个方法，在迷宫地图中寻找通路”

她噼里啪啦一顿操作就写完了，代码如下：

public class Maze { 
    
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
    
            int i; // 横坐标
            int j; // 纵坐标
    
            // 创建一个10×10的迷宫地图
            int[][] map = new int[10][10];
    
            // 设置迷宫地图的左、右两边为墙，用“1”来代替墙面
            for (i = 0; i < 10; i++) { 
                map[i][0] = 1;
                map[i][9] = 1;
            }
    
            // 设置迷宫地图的上、下两边为墙，用“1”来代替墙面
            for (i = 0; i < 10; i++) { 
                map[0][i] = 1;
                map[9][i] = 1;
            }
    
            // 设置迷宫地图中的挡板位置
            map[4][1] = 1;
            map[4][2] = 1;
            map[4][3] = 1;
    
            System.out.println("迷宫地图的情况：");
            for (i = 0; i < 10; i++) { 
                for (j = 0; j < 10; j++) { 
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
    
            System.out.println("输入小明的起始点 m:");
            int m = scanner.nextInt();
    
            System.out.println("输入小明的起始点 n:");
            int n = scanner.nextInt();
    
            // 寻找迷宫的出路
            mazeTrack(map, m, n);
    
            System.out.println("小明走过，并标识的迷宫地图的情况：");
            for (i = 0; i < 10; i++) { 
                for (j = 0; j < 10; j++) { 
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        /** * @param maze 表示迷宫地图 * @param i 小明从哪个位置开始找 * @param j 小明从哪个位置开始找 * @return 如果小明找到了通路，就返回true */
        public static boolean mazeTrack(int[][] maze, int i, int j) { 
            if (maze[8][8] == 2) {  // 如果迷宫中的（8,8）这个点标记为“2”，则说明小明已经找到了出口
                return true;
            } else { 
                if (maze[i][j] == 0) {  // 当前这个点还没走过
                    maze[i][j] = 2;
                    if (mazeTrack(maze, i - 1, j)) {  // 探索向上走是否可行
                        return true;
                    } else if (mazeTrack(maze, i, j + 1)) {  // 探索向右走是否可行
                        return true;
                    } else if (mazeTrack(maze, i + 1, j)) {  // 探索向下走是否可行
                        return true;
                    } else if (mazeTrack(maze, i, j - 1)) {  // 探索向左走是否可行
                        return true;
                    } else { 
                        // 如果在探索过程中该点走不通，则标记为“3”
                        maze[i][j] = 3;
                        return false;
                    }
    
                } else { 
                    return false;
                }
            }
        }
    }

***代码执行结果：***  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 2]

看着运行结果，她满脸微笑，看着很开心的样子！O(∩\_∩)O哈哈~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 3]

**我**：如果改变寻找路的策略，如果在走下一步的时候 按向下、向右、向上、向左这样走，结果会是啥样的。

**她**：那我修改一下代码

public static boolean mazeTrack(int[][] maze, int i, int j) { 
            if (maze[8][8] == 2) {  // 通路已经找到
                return true;
            } else { 
                if (maze[i][j] == 0) {  // 当前这个点还没走过
                    maze[i][j] = 2;
                    if (mazeTrack(maze, i + 1, j)) {  // 探索向下走是否可行
                        return true;
                    } else if (mazeTrack(maze, i, j + 1)) {  // 探索向右走是否可行
                        return true;
                    } else if (mazeTrack(maze, i - 1, j)) {  // 探索向上走是否可行
                        return true;
                    } else if (mazeTrack(maze, i, j - 1)) {  // 探索向左走是否可行
                        return true;
                    } else { 
                        // 该点走不通，标记为“3”
                        maze[i][j] = 3;
                        return false;
                    }
    
                } else { 
                    return false;
                }
            }
        }

代码执行结果：

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

**我**：“你看，寻找通路的时候制定的策略不一样，最后走的路也不一样。`这儿涉及到最短路径的问题，等下一次给你再讲`”

--------------------

***由于水平有限，本博客难免有不足，恳请各位大佬不吝赐教！***

[Link 1]: https://zhangxy.blog.csdn.net/article/details/104496630
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200302122257234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw==,size_16,color_FFFFFF,t_70
[20200228164652287.png]: https://img-blog.csdnimg.cn/20200228164652287.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200302124224905.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw==,size_16,color_FFFFFF,t_70
[20200302125658983.png]: https://img-blog.csdnimg.cn/20200302125658983.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200228171058219.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200302132507145.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3MDM2Nw==,size_16,color_FFFFFF,t_70
[20200302141342658.png]: https://img-blog.csdnimg.cn/20200302141342658.png