「迷宫问题」队列+BFS与栈+DFS分别求解

绝地灬酷狼 2022-05-24 03:24 212阅读 0赞

# 1 迷宫问题 #

一个迷宫如图所示，他有一个入口和一个出口，其中白色单元表示通路，黑色单元表示不通路。试寻找一条从入口到出口的路径，每一部只能从一个白色单元走到相邻的白色单元，直至出口。

![70][]  
迷宫问题

# 2 简介BFS和DFS #

BFS全称Breadth First Search，即广度优先搜索。搜索目标时逐层展开遍历，一旦找到目标则终止，过程类似树的层次遍历。  
DFS全称Depth First Search，即深度优先搜索。搜索目标时只选择一个方向进行探索，进入死路（ps：找不到目标）则回溯，因此需要基于栈的机制进行。  
基于这两种算法的特点，可以知道BFS求解迷宫得出的结果为最短路径，而DFS则不一定。  
这里只是简单介绍这两种算法。

# 3 开始前的规定 #

1 maze二维数组表示迷宫，0表示不通路，1表示通路，2表示访问过
    2 定义迷宫的坐标点
    public class Point {
    
        /** 横坐标 */
        private int x;
        /** 纵坐标 */
        private int y;
    
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public int getX() {return x;}
        public void setX(int x) {this.x = x;}
        public int getY() {return y;}
        public void setY(int y) {this.y = y;}
    
        /** 向右转，起步走 停 */
        public Point right() {return new Point(x + 1, y);}
    
        /** 向左转，起步走 停 */
        public Point left() {return x == 0 ? null : new Point(x - 1, y);}
    
        /** 起步走 停 */
        public Point up() {return y == 0 ? null : new Point(x, y - 1);}
    
        /** 向后转，起步走 停 */
        public Point down() {return new Point(x, y + 1);}
    
        @Override
        public boolean equals(Object o) {
            if (this == o) { return true; }
            if (o == null || getClass() != o.getClass()) { return false; }
    
            Point point = (Point) o;
    
            return (x == point.x) && (y == point.y);
        }
    
        @Override
        public int hashCode() {
            int result = 17;
            result = 31 * result + x;
            result = 31 * result + y;
            return result;
        }
    }

# 4 队列+BFS求解 #

思路：
    1 从当前坐标出发，获取所有能访问的方向的坐标点并存入队列中。
    2 使用一个二维数组作为前驱节点标记，记录访问这些方向坐标点的前访问的坐标，也就是当前坐标。
    3 判断这些方向的坐标点是否有是出口的，是则终止循环；反之重新循环。
    4 循环终止时通过前驱结点标记坐标，找到访问出口坐标的前访问的上一节点，依次，最后到入口节点，得到路径。

**Java实现代码：**

/**
     * 队列与BFS算法求解迷宫最短路径
     * @param maze 迷宫
     * @param start 入口
     * @param end 出口
     * @return false表示无解
     */
    public boolean solveByQ(int[][] maze, Point start, Point end) {
    
        // api调用者搞事
        if (maze == null || start == null || end == null ||
            maze[start.getY()][start.getX()] != ACCESS || maze[end.getY()][end.getX()] != ACCESS) {
            throw new IllegalArgumentException(ERROR_CODE);
        }
        // 起点即终点
        if (start.equals(end)) { return true; }
    
        // 前驱标记，起标记上个坐标和标记被访问的作用，记录访问当前坐标时的前一个坐标，null时表示当前坐标未被访问
        Point[][] preMark = new Point[maze.length][maze[0].length];
    
        // 存储即将被遍历的节点
        Queue<Point> visitingPoints = new LinkedList<>();
        visitingPoints.add(start);
    
        while (!visitingPoints.isEmpty()) {
            // 取出队首元素，作为当前起点坐标
            Point current = visitingPoints.poll();
    
            // 探寻当前坐标的 ↑→↓← 是否通路且是否未被访问过，符合条件则加入队列等待被访问
            // ↑
            Point up = current.up();
            if (up != null &&
                maze[up.getY()][up.getX()] == ACCESS &&
                preMark[up.getY()][up.getX()] == null) {
                // 向上走通路，且上节点未被访问，做个标记
                preMark[up.getY()][up.getX()] = current;
                visitingPoints.add(up);
                // 到终点则跳出循环
                if (up.equals(end)) { break; }
            }
            // →
            Point right = current.right();
            if (right.getX() < maze[0].length &&
                maze[right.getY()][right.getX()] == ACCESS &&
                preMark[right.getY()][right.getX()] == null) {
    
                preMark[right.getY()][right.getX()] = current;
                visitingPoints.add(right);
                if (right.equals(end)) { break; }
            }
            // ↓
            Point down = current.down();
            if (down.getY() < maze.length &&
                maze[down.getY()][down.getX()] == ACCESS &&
                preMark[down.getY()][down.getX()] == null) {
    
                preMark[down.getY()][down.getX()] = current;
                visitingPoints.add(down);
                if (down.equals(end)) { break; }
            }
            // ←
            Point left = current.left();
            if (left != null &&
                maze[left.getY()][left.getX()] == ACCESS &&
                preMark[left.getY()][left.getX()] == null) {
    
                preMark[left.getY()][left.getX()] = current;
                visitingPoints.add(left);
                if (left.equals(end)) { break; }
            }
        }
    
        // 找不到出口
        if (visitingPoints.isEmpty()) { return false; }
    
        // 验证标记路径从出口找回入口
        Point p = end;
        while (!p.equals(start)) {
            maze[p.getY()][p.getX()] = VISITED;
            p = preMark[p.getY()][p.getX()];
        }
        maze[p.getY()][p.getX()] = VISITED;
        return true;
    }

# 5 栈+DFS求解 #

思路：
    1 设立一个二维数组作为访问标记，标记访问过或者不通路的坐标
    2 从栈中取出当前坐标，获取下一步方向坐标点。
    3 如果获取不到，说明走到死路，回溯，重新循环。
    4 如果获取到，将这个下一步方向坐标点打上标记，并加入栈中，重新循环。

**Java实现代码：**

/**
     * 栈与DFS算法求解迷宫路径，非最短路径
     * @param maze 迷宫
     * @param start 起点
     * @param end 终点
     * @return false表示无解
     */
    public boolean solveByStack(int[][]maze, Point start, Point end) {
    
        // api调用者搞事
        if (maze == null || start == null || end == null ||
                maze[start.getY()][start.getX()] != ACCESS || maze[end.getY()][end.getX()] != ACCESS) {
            throw new IllegalArgumentException(ERROR_CODE);
        }
        // 起点即终点
        if (start.equals(end)) { return true; }
    
        // 访问标记，起标记当前坐标是否被访问过或者不通路，访问过或者不通路的标记为true
        boolean[][] visitedMark = new boolean[maze.length][maze[0].length];
        for (int i = 0; i < visitedMark.length; i++) {
            for (int j = 0; j < visitedMark[i].length; j++) {
                visitedMark[i][j] = (maze[i][j] == NO_ACCESS);
            }
        }
    
        // 存储被遍历的节点
        Stack<Point> visitedPoints = new Stack<>();
        visitedPoints.push(start);
    
        // 非空栈，且未到出口
        while (!visitedPoints.isEmpty() && !end.equals(visitedPoints.peek())) {
            // 获取下一步
            Point nextPoint = getNextPoint(visitedMark, visitedPoints.peek());
            // 如果走到死路，则回溯
            if (nextPoint == null) {
                visitedPoints.pop();
                continue;
            }
    
            // 否则标记下一步坐标
            visitedMark[nextPoint.getY()][nextPoint.getX()] = true;
            visitedPoints.add(nextPoint);
        }
    
        // 找不到出口
        if (visitedPoints.isEmpty()) { return false; }
    
        // 从出口寻回入口
        while (!visitedPoints.isEmpty()) {
            Point p = visitedPoints.pop();
            maze[p.getY()][p.getX()] = VISITED;
        }
    
        return true;
    }
    
    /**
     * 辅助solveByStack方法，获取当前坐标的相邻可行节点作为下一步坐标
     * @param visitedMark 访问标记的二维数组
     * @param current 当前坐标点
     * @return 下一步坐标点
     */
    private Point getNextPoint(boolean[][] visitedMark, Point current) {
        // 上节点通路
        Point up = current.up();
        if (up != null && !visitedMark[up.getY()][up.getX()]) { return up; }
    
        // 右节点通路
        Point right = current.right();
        if (right.getX() < visitedMark[0].length && !visitedMark[right.getY()][right.getX()]) { return right; }
    
        // 下节点通路
        Point down = current.down();
        if (down.getX() < visitedMark.length && !visitedMark[down.getY()][down.getX()]) { return down; }
    
        // 左节点通路
        Point left = current.left();
        if (left != null && !visitedMark[left.getY()][left.getX()]) { return left; }
    
        // 死路
        return null;
    }

# 6 最后 #

感谢阅读，代码已放在github。  
[https://github.com/hdonghong/square-wheels/blob/master/data-structure/lab3/impl/MazeSolution.java][https_github.com_hdonghong_square-wheels_blob_master_data-structure_lab3_impl_MazeSolution.java]

[70]: /images/20220524/42c8d2956f3a433887fa76dabbf9be7b.png
[https_github.com_hdonghong_square-wheels_blob_master_data-structure_lab3_impl_MazeSolution.java]: https://github.com/hdonghong/square-wheels/blob/master/data-structure/lab3/impl/MazeSolution.java