深度优先搜索与广度优先搜索

对于走迷宫问题，可能我们经常用的是深度优先搜索，本来我对学习的态度是只要知道一种处理办法就行了，可是我想到在街上找厕所的时候，想一想还是看一下最短路径是怎么弄的吧
接下来先来看一下深度优先搜索
首先对于一个迷宫，1是墙，0是路如下图所示

image.png
那么对于深度优先搜索我先采取递归的方式来求解这个问题
首先来进行几个约定在求解之前，1代表墙，0代表没有走过的路，2代表走过的路，3代表该路不通
这个递归里面应该传入这个地图也就是这个矩阵数组，和当前所处的位置
1).首先判断目的地是否为2，如果为2则表示已有路可达，返回true
2).如果没有则判断当前位置是否为0，如果为0则继续探行
2-1).根据此点往四处寻找，如果某一处返回true，则该分支返回true，否则将此点设置为3并且返回为false
3).如果不是则返回false（可能出现1，2，3）
代码如下

public class Migong {
    public static void main(String[] args) {
        int[][] map = new int[8][7];
        for(int i=0;i<8;i++){
            map[i][0] = 1;
            map[i][6] = 1;
        }
        for(int i=0;i<7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;
        sout(map);
        dept(map,1,1);
        System.out.println();
        sout(map);
    }
    public static void sout(int[][] map){
        for(int[] row:map){
            for(int item:row){
                System.out.print(item + "  ");
            }
            System.out.println();
        }
    }
    public static boolean dept(int[][] map,int i, int j){
        if(map[6][5]==2){
            return true;
        }else {
            if(map[i][j] == 0){
                map[i][j] = 2;
                if(dept(map,i+1,j)){
                    return true;
                }else if(dept(map,i,j+1)){
                    return true;
                }else if(dept(map,i-1,j)){
                    return true;
                }else if (dept(map,i,j-1)){
                    return true;
                }else {
                    map[i][j] = 3;
                    return false;
                }
            }else {
                return false;
            }
        }
    }
}

运行结果如下

image.png

接下来探讨最短路径，最短路径应该是有由一个点往四处扩展，在某一层如果某一个点探寻到了，则为最短路径（深度最小），因为在这一层以前还没有答案，所以为最短
具体细节我们可以：
1.创建一个类保存走过的路径以及和上一个点的数据
1.创建一个队列，并将起始位置入队
2.将队列里面的取出一个点往四处探寻，为0的入队列
3.判断入队列的点是不是终点，是则停止
4.将2-3反复调用
代码如下，输出路径从下往上看（数据结构和算法的新手，请勿喷）

public class BreadMigong {
    private static Queue<Step> queue = new ArrayDeque<>();
    public static void main(String[] args) {
        int[][] map = new int[8][7];
        for(int i=0;i<8;i++){
            map[i][0] = 1;
            map[i][6] = 1;
        }
        for(int i=0;i<7;i++){
            map[0][i] = 1;
            map[7][i] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;

        queue.add(new Step(1,1,null));
        Step res = null;
        while (!queue.isEmpty()){
            Step step = queue.poll();
            res = toNext(step, map,1,0);
            if(res != null)
                break;
            res = toNext(step, map,-1,0);
            if(res != null)
                break;
            res = toNext(step, map,0,1);
            if(res != null)
                break;
            res = toNext(step, map,0,-1);
            if(res != null)
                break;
        }
        while (res != null){
            System.out.println(res.getRow() + " " + res.getCol());
            res = res.getPri();
        }
    }
    public static Step toNext(Step step,int[][] map, int i, int j){
        if(map[step.getRow() + i][step.getCol() + j] == 0){
            Step temp = new Step(step.getRow() + i, step.getCol() + j, step);
            queue.add(temp);
            map[step.getRow() + i][step.getCol() + j] = 2;
            if(map[6][5] == 2) {
                return temp;
            }
        }
        return null;
    }
}
class Step{
    private int row;
    private int col;
    private Step pri;
    public Step(int row, int col, Step pri) {
        this.row = row;
        this.col = col;
        this.pri = pri;
    }
    public int getRow() {
        return row;
    }
    public void setRow(int row) {
        this.row = row;
    }
    public int getCol() {
        return col;
    }
    public void setCol(int col) {
        this.col = col;
    }
    public Step getPri() {
        return pri;
    }
    public void setPri(Step pri) {
        this.pri = pri;
    }
    @Override
    public String toString() {
        return "Step{" +
                "row=" + row +
                ", col=" + col +
                '}';
    }
}