BFS入门，Java迷宫问题

这其实是BFS的入门级问题，我以初学者的姿态研究，如有不足请指正。

BFS的核心是利用query的先进先出原则，而本题的回溯用到了stack的后进先出原则，可以说是对两种数据结构的复习。

在解题过程中对Java的对象复制的本质有了更加深刻的理解，具体发在另一篇博文”Java对象复制的背后“

本题是基本的BFS原理，附加利用二维数组构造象限，利用二维boolean数组构造visited，和利用二维dir数组构建上下左右的移动。

以下是代码

这里的queue是存放每层点的数据结构。（从上一层前往下一层），有且它只保存一层的数据。这也符合BFS的特质。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class solution {
        public static int M = 5;
        public static int N = 5;

        public static void main(String args[]) {

                int maze[][] = { { 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 } };
                if (maze_path(maze))
                        System.out.println("The solution is showed above");
                else
                        System.out.println("It is not feasible");

        }

        public static boolean maze_path(int MAZE[][]) {
                int maze[][] = MAZE;
                boolean visited[][] = new boolean[5][5];
                Queue<Node> queue = new LinkedList<Node>();
                Stack<Node> path = new Stack<Node>();
                Node start = new Node(0, 0);
                visited[0][0] = true;
                Node end = new Node(4, 4);
                Node cur = new Node(0, 0, 0, 0);
                Node move = new Node(0, 0, 0, 0);
                int dir[][] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
                queue.offer(start);

                while (!queue.isEmpty()) {
                        cur = queue.poll();
                        path.push(cur);

                        for (int i = 0; i < 4; i++) {
                                move.x = cur.x + dir[i][0];
                                move.y = cur.y + dir[i][1];
                                move.prev_x = cur.x;
                                move.prev_y = cur.y;

                                if (move.x == end.x && move.y == end.y) {
                                        while (!path.isEmpty()) {
                                                Node show_path = path.pop();
                                                if (move.prev_x == show_path.x && move.prev_y == show_path.y) {
                                                        System.out.println("(" + show_path.x + ", " + show_path.y + ")");
                                                        move = show_path;
                                                }
                                        }

                                        return true;
                                }

                                if (move.x >= 0 && move.x < M && move.y >= 0 && move.y < N && (maze[move.x][move.y] == 0)
                                                && (!visited[move.x][move.y])) {
                                        Node new_node = new Node(move.x, move.y, move.prev_x, move.prev_y);
                                        queue.offer(new_node);
                                        visited[move.x][move.y] = true;
                                }
                        }
                }
                return false;
        }
}

　　以下是Node类

public class Node {
        public int x;
        public int y;
        public int prev_x;
        public int prev_y;
        boolean value;
        public Node(int X, int Y, int PREV_X, int PREV_Y) {
                this.x = X;
                this.y = Y;
                this.prev_x = PREV_X;
                this.prev_y = PREV_Y;
        }
        public Node(int X, int Y) {
                this.x = X;
                this.y = Y;
        }

}

　　值得注意的是，为了回溯的需要，在node中还添加了prev_x和prev_y

在解题过程中我在思路上遇到过两个瓶颈

1. 最初我认为BFS的算法不能解决这个迷宫问题，当时的想法是：比如总有一个点是一条岔路，然后有一条看似能走通的路和一条不能走通的路，如果通过标记点的方式，可能在不能走通的路上把能走通的点标为了false，于是都走不通了。其实这个想法仔细想想就不可能，因为如果那条所谓不能走通的路上存在一个能够让另一条路走通的点，那么它本身就肯定是能够走通的。现在看起来很容易的point，当时确实困扰了我很久。

2. 在回溯时，利用

while (!path.isEmpty()) {
                                                Node show_path = path.pop();
                                                if (move.prev_x == show_path.x && move.prev_y == show_path.y) {
                                                        System.out.println("(" + show_path.x + ", " + show_path.y + ")");
                                                        move = show_path;
                                                }
                                        }
这段代码可以完成回溯，通过stack的先进后出原则，通过回溯到上一个节点的prev则能够继续找到更上一个的，进而完成全部回溯。