Java数据结构-迷宫回溯问题 蓝桥必备

        鸽了一天之后的博主,今天终于良心发现,打开了尘封的博客,给大家带来了今天的博客

         今天我要介绍的是什么呢,故名思议,迷宫回溯问题,迷宫回溯问题其实相当于是对递归回溯的深度理解,将前面我发的八皇后问题理解通透后回头再看看迷宫回溯问题,嗯?这不是有手就行吗!

        那跟随着博主的脚步,从 迷宫问题的概述 -> 迷宫问题的思路分析 -> 迷宫问题的代码实现与分析 -> 总结 开始学习我们的迷宫回溯问题吧!

        如果喜欢博主记得点赞哦,如果可以的话,给博主一个小小的关注.

往期精彩:

        八皇后问题

        在一个迷宫中,我们要通过我们的程序,让一个小球在起点出发,绕过重重障碍,找到出口,这就是著名的迷宫问题.

        在本届蓝桥杯备赛中,作为c++的B组(我报错了,别问我为什么不说Java),显赫的提出了迷宫回溯问题!除了在大赛中出现,迷宫回溯问题也是我们更好的理解递归和回溯的重要途经.

首先:我们要做的第一步就是创建一个迷宫,我们可以通过二维数组去实现其次:我们要做出某些约定 如下1) 1表示围墙 2) 2表示已经走过的通路 3)3表示此路不通 4) 0表示该路没有走过创建一个回溯方法去找路制定一个策略(本人采用的是 下 → 右 → 上 → 左)

创建一个迷宫 

 var maze = new int[8][7];
        for (int i = 0; i < maze.length; i++) {
            maze[i][0] = 1;
            maze[i][6] = 1;
        }
        for (int i = 0; i < maze[0].length; i++) {
            maze[0][i] = 1;
            maze[7][i] = 1;
        }
        maze[3][1] = 1;
        maze[3][2] = 1;
        maze[3][3] = 1;
        for(var arr : maze) {
            for(var ele : arr) {
                System.out.print(ele + " ");
            }
            System.out.println();
        }

代码分析:

第一个for循环的目的是创建两列围墙,如图所示

第二个for是的目的是创建两行围墙,如图所示

下面的赋值是为了增加障碍,这个可按个人的喜好增加,本人加过的障碍如图所示 

 创建一个方法去走

public static boolean searchRood(int[][] maze,int srcRow,int srcCol) {
        if(maze[6][5] == 2) {
            return true;
        }
        if(maze[srcRow][srcCol] == 0) {
            maze[srcRow][srcCol] = 2;
            if(searchRood(maze,srcRow+1,srcCol)) {
                return true;
            }else if(searchRood(maze,srcRow,srcCol+1)) {
                return true;
            }else if(searchRood(maze,srcRow-1,srcCol)) {
                return true;
            }else if(searchRood(maze,srcRow,srcCol-1)) {
                return true;
            }else {
                maze[srcRow][srcCol] = 3;
            }
        }
        return false;
    }

代码分析:

maze传递的是二维数组,即迷宫,因为数组是对象,存放在堆内存空间,有利于多个方法同时对该数组作出修改srcRow与SrcCol为开始的坐标 第一个判断的目的是,如果终点被标识了2,说明终点已经到了,方法结束第二个判断是没有走过的情形,由下图分析代码目的:(建议边看代码边看图,图是根据代码实现的,且我们需要培养假设的思想)

 结合两个图一起看,最后是可以光所有的栈的注意:1表示围墙,不能走,弹栈  2表示已经走过,没必要走,弹栈 3表示死路,不能走,弹栈  完整代码

package datastructure.chapter02.recursion.maze;

public class MazeBackTrackingDemo {

    public static void main(String[] args) {
        var maze = new int[8][7];
        for (int i = 0; i < maze.length; i++) {
            maze[i][0] = 1;
            maze[i][6] = 1;
        }
        for (int i = 0; i < maze[0].length; i++) {
            maze[0][i] = 1;
            maze[7][i] = 1;
        }
        maze[3][1] = 1;
        maze[3][2] = 1;
        maze[3][3] = 1;
        for(var arr : maze) {
            for(var ele : arr) {
                System.out.print(ele + " ");
            }
            System.out.println();
        }
        searchRood(maze,1,1);
        System.out.println();
        for(var arr : maze) {
            for(var ele : arr) {
                System.out.print(ele + " ");
            }
            System.out.println();
        }
    }

    
    public static boolean searchRood(int[][] maze,int srcRow,int srcCol) {
        if(maze[6][5] == 2) {
            return true;
        }
        if(maze[srcRow][srcCol] == 0) {
            maze[srcRow][srcCol] = 2;
            if(searchRood(maze,srcRow+1,srcCol)) {
                return true;
            }else if(searchRood(maze,srcRow,srcCol+1)) {
                return true;
            }else if(searchRood(maze,srcRow-1,srcCol)) {
                return true;
            }else if(searchRood(maze,srcRow,srcCol-1)) {
                return true;
            }else {
                maze[srcRow][srcCol] = 3;
            }
        }
        return false;
    }

}

        迷宫回溯问题总体代码量仍是很少的,对代码的解析主要在图中,想要真正理解其中的回溯思想,还是得自己也尝试动手画一下内存图

        总结一下必须掌握的几点:理解回溯和递归的场景

下一站:单向链表