华为oj迷宫问题求解（深度优先搜索和广度优先搜索）

深度优先搜索：

自己花了好长时间学习了深度优先搜索算法，受益颇多，网上许多资料都看不太懂，最后自己按着那个思想一步一步实现了，分享一下，以华为 oj 上的迷宫问题为例来说一下：

问题描述：

定义一个二维数组 N*M （其中 2<=N<=10;2<=M<=10 ），如 5×5 数组下所示：

int maze[5][5]={ 0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0, };

它表示一个迷宫，其中的 1 表示墙壁， 0 表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为 [0,0], 既第一空格是可以走的路。

Input 一个 N × M 的二维数组，表示一个迷宫。数据保证有唯一解 , 不考虑有多解的情况，即迷宫只有一条通道。 Output 左上角到右下角的最短路径，格式如样例所示。

Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

Sample Output (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)

输入描述：

输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的 1 表示墙壁， 0 表示可以走的路。数据保证有唯一解 , 不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

输入例子：

5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0

输出例子：

(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)

之前我们求最短路径用的广度优先搜索，这个题看似是最短路径问题，其实不是，因为题目上说了只有一条通路，而且还要输出这个路径，那么深度优先搜索比较合适，当然广度优先搜索也可以。深度优先搜索的思想是沿着一个方向搜到底，如果行不通，则返回来试其他的路径。就一直这样直到找到一条通路输出就可以了。其实这个思想网上一大堆，但是具体怎么实现呢？下面我贴上自己的代码，代码中会有详细的注释：

import java.util.Scanner;
import java.util.Stack;
public class Main {
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[][] map = new int[m][n];// 定义一个Map矩阵，用来保存地图
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j] = sc.nextInt();// 输入地图
                }
            }
            int[][] dir = {{1, 0}, {0, 1}};// 定义两个方向横着走或者竖着走（题目中说只走这两个方向，当然也可以定义多个方向）
            Stack<Node> stack = new Stack<Node>();// 定义一个栈，保存路径
            int[][] visited = new int[m][n];// 标记是否被访问，这个要和Map大小对应
            Node start = new Node(0, 0);// 定义起始位置
            Node end = new Node(m - 1, n - 1);// 定义目的位置
            visited[start.x][start.y] = 1;// 将起始点标记为访问
            stack.push(start);// 将起始点加入队列
            while (!stack.isEmpty()) {// 如果对了为空了还没有找到解，说明就没有通路，当然本题不存在无解，题目上说了一定存在一个通路。
                boolean flag = false;// 标记是否找了一个方向
                Node pek = stack.peek();// 获取栈顶元素，注意不需要出栈
                if (pek.x == end.x && pek.y == end.y) {// 如果到达目的地则跳出循环
                    break;
                } else {
                    for (int i = 0; i < 2; i++) {// 循环两个方向
                        Node nbr = new Node(pek.x + dir[i][0], pek.y + dir[i][1]);// 找到当前位置的邻居位置坐标并判断是否合法
                        if (nbr.x >= 0 && nbr.x < m && nbr.y >= 0 && nbr.y < n && map[nbr.x][nbr.y] == 0 && visited[nbr.x][nbr.y] == 0) {// 判断邻居节点是否合法
                            stack.push(nbr);// 合法将邻居位置加入栈
                            visited[nbr.x][nbr.y] = 1;// 并标记该节点已经访问
                            flag = true;// 找到了一个方向
                            break;// 找到了就停止循环，顺着这个方向一直搜索
                        }
                    }
                    if (flag) {// 找到了方向，就不用执行下面的出栈，沿着这个方向一直搜下去
                        continue;
                    }
                    stack.pop();// 如果两个方向都不能通过，则出栈。
                }
            }
            Stack<Node> stkRev = new Stack<Node>();// 将路径反过来，因为栈中输出的路径是反的
            while (!stack.isEmpty()) {
                stkRev.push(stack.pop());
            }
            while (!stkRev.isEmpty()) {
                System.out.println("(" + stkRev.peek().x + "," + stkRev.peek().y + ")");
                stkRev.pop();
            }
        }
    }
}
class Node{
    int x;
    int y;
    Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}

广度优先搜索：

一般谈起广搜，我的第一反应就是求最短路径，因为广搜是由内向外逐层扩散，最后肯定能找到一个最短的路径，其实用法也不难，今天说的广搜和之前的不同之处在于，之前求最短路径，最终只需给出一个数字表示最短的长度，而不需要输出具体的路径是什么，也就是怎么走，而今天的广搜是需要输出路径，要是谈起这个路径问题，我想大部分人可能觉得深搜比较好，的确，我也是这样觉得，但是我们要灵活运行多种方法去解决一个问题，下来说说具体的题目吧。

广搜的套路就是利用一个队列，每次将当前点的邻居节点加入队列，然后出队，在将当前点加入队列，一直讲所有路径搜索完毕，直到队列为空停止。同时还需要一个数组去保存该节点是否访问，做个标记。但是怎样输出路径呢，我采取的办法是每次我们需要保存一下当前节点的前驱节点，可以这样设计一个类保存当前坐标和前驱坐标：

class Node{

int x;

int y;

int prex;

int prey;

}

这样最终我们可以通过前驱节点来输出整个的路径。具体怎样做请往下看，就拿迷宫问题给的样例来说吧，每次将所有出队的节点保存在一个 arrayList 中，最终 arrayList 中保存了所有出队的节点，我们怎样从这些节点确定一条路径呢？
输入 5 5

0 1 0 0 0

0 1 0 1 0

0 0 0 0 0

0 1 1 1 0

0 0 0 1 0

arrayList 中会保存 13 个节点，分别是

（ 0,0,0,0 ）

（ 1,0,0,0 ）

（ 2,0,1,0 ）

（ 3,0,2,0 ）

（ 2,1,2,0 ）

（ 4,0,3,0 ）

（ 2,2,2,1 ）

（ 4,1,4,0 ）

（ 2,3,2,2 ）

（ 4,2,4,1 ）

（ 2,4,2,3 ）

（ 3,4,2,4 ）

（ 4,4,3,4 ）

前两个坐标代表当前坐标位置，后两个代表前驱坐标位置，然后按照从目的节点往起始节点找路径，如下图：

这样最终找到了一条路径 (0,0) （ 1,0)(2,0)(2,1)(2,2)(2,3)(2,4)(3,4)(4,4) ，即是我们最终要求解的问题。这样广度搜索也实现了路径的问题，下来就是写代码了，具体怎么实现每个人都不一样，下面贴上我自己的代码：

import java.util.*;
public class BFS {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int m=sc.nextInt();
            int n=sc.nextInt();
            int[][] map = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    map[i][j] = sc.nextInt();
                }
            }
            int[][] dir = {{1, 0}, {0, 1}};
            int[][] visited=new int[m][n];
            Node start=new Node(0,0);
            Node end=new Node(m-1,n-1);
            Queue<Node> queue=new LinkedList<Node>();
            ArrayList<Node> arrayList=new ArrayList<Node>();// 用来保存每一个出队列的节点
            queue.offer(start);
            while (!queue.isEmpty()){
                Node local=queue.remove();
                arrayList.add(local);
                for (int i=0;i<2;i++){
                    Node nbr=new Node(local.x+dir[i][0],local.y+dir[i][1]);
                    if(nbr.x>=0&&nbr.x<m&&nbr.y>=0&&nbr.y<n&&map[nbr.x][nbr.y]==0&&visited[nbr.x][nbr.y]==0){
                        visited[nbr.x][nbr.y]=1;
                        queue.offer(nbr);
                        nbr.prex=local.x;// 保存前驱节点
                        nbr.prey=local.y;// 保存前驱节点
                    }
                }
            }
            Stack<Integer> stack=new Stack<Integer>();
            int  px=arrayList.get(arrayList.size()-1).prex;// 获得目的节点的前驱节点
            int  py=arrayList.get(arrayList.size()-1).prey;
            stack.push(arrayList.size()-1);// 将目的节点在arrayList中的位置记录下来，便于输出
            while (true){
                if(px==0&&py==0){// 找到起始节点就停止
                    break;
                }
                for(int i=0;i<arrayList.size();i++){// 循环找出每一个节点的前驱，找到就跳出当前循环
                    if(arrayList.get(i).x==px&&arrayList.get(i).y==py){
                        px=arrayList.get(i).prex;
                        py=arrayList.get(i).prey;
                        stack.push(i);// 保存节点在arrayList中的位置
                        break;
                    }
                }
            }
            System.out.println("(0,0)");
            while (!stack.isEmpty()){
                System.out.println("("+arrayList.get(stack.peek()).x+","+arrayList.get(stack.peek()).y+")");
                stack.pop();
            }
        }
    }
}
class Node{
    int x;
    int y;
    int prex;// 保存前驱节点位置
    int prey;
    Node(int x,int y){
        this.x=x;
        this.y=y;
    }
}