目录

迷宫最短路径

题目

如下图所示的一个迷宫,其中#表示墙,T表示出口,S表示起点,请输出S到T的最短路径并用".“标记最短路径。 https://gitee.com/lienhui68/picStore/raw/master/null/20200701003403.png

解题思路

我们都知道BFS可以很简单求出最短路径的值,但是又怎样输出它的最短路径呢?我们可以构建一个坐标类型的二维数组pre[x][y],记录每个节点的前驱顶点是哪个顶点。因为每个节点的前驱节点是唯一的,只会是最快到达它的那个顶点,而每个节点的后继节点却不唯一,它可能可以朝各个方向走,所以记录它的前驱节点是可行的。然后就是输出问题,我们需要递归逆序输出就可以了。

代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package com.eh.ftd.dsa.ds;

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

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/30 22:57
 */
public class Maze1 {

    // 迷宫
    private char[][] maze;
    // 4个方向
    int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    // 是否走过
    boolean[][] visited;
    // 记录走到当前坐标的上一坐标
    Pos[][] pre;

    static class Pos {
        int x;
        int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public Maze1(char[][] maze) {
        this.maze = maze;
        this.visited = new boolean[maze.length][maze[0].length];
        this.pre = new Pos[maze.length][maze[0].length];
    }

    /**
     * 寻找迷宫最短路径
     *
     * @param start
     */
    public Pos bfs(Pos start) {
        Queue<Pos> queue = new LinkedList<>();
        // 起点入队
        queue.offer(start);
        // 当前坐标
        Pos cur;
        while ((cur = queue.poll()) != null) {
            visited[cur.x][cur.y] = true;
            // 上下左右试探
            for (int i = 0; i < 4; i++) {
                int x = cur.x + dir[i][0];
                int y = cur.y + dir[i][1];
                // 坐标是否在迷宫内部
                boolean in = x < maze.length && y < maze[0].length;
                if (in && maze[x][y] == 'T') {
                    // 记录父坐标
                    pre[x][y] = cur;
                    // 找到出口
                    return new Pos(x, y);
                }
                // 坐标在迷宫内部 && 没被访问过 && 可通行
                if (in && !visited[x][y] && maze[x][y] == ' ') {
                    // 入队
                    queue.offer(new Pos(x, y));
                    // 记录父坐标
                    pre[x][y] = cur;
                }
            }
        }
        return null;

    }

    public void markTheShortestPath(Pos cur) {
        // 终点的上一个节点; 不是起点坐标; 上一个节点
        for (cur = pre[cur.x][cur.y]; maze[cur.x][cur.y] != 'S'; cur = pre[cur.x][cur.y]) {
            // *标记最短通路
            maze[cur.x][cur.y] = '.';
        }
    }

    public void printTheShortestPath(Pos cur) {
        if (maze[cur.x][cur.y] == 'S') {
            System.out.printf("{%d,%d}", cur.x, cur.y);
            return;
        }
        printTheShortestPath(pre[cur.x][cur.y]);
        System.out.printf("{%d,%d}", cur.x, cur.y);
    }

    private void displayMazePath() {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                System.out.print(maze[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

        /**
         * 迷宫
         * # 挡板
         * S 起点
         * T 出口
         */
        char[][] map = {
                {'#', '#', '#', '#', '#', '#', '#', '#', 'T', '#', '#', '#'},
                {'#', 'S', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#'},
                {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', '#', '#', ' ', '#'},
                {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', ' ', ' ', '#'},
                {'#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', '#', ' ', '#'},
                {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
                {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},
                {'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', ' ', ' ', '#'},
                {'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},
                {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},
        };


        Maze1 maze = new Maze1(map);
        Pos ter = maze.bfs(new Pos(1, 1));
        maze.markTheShortestPath(ter);
        maze.displayMazePath();
        System.out.println("最短路径:");
        maze.printTheShortestPath(ter);
    }


}

运行结果: https://gitee.com/lienhui68/picStore/raw/master/null/20200701003549.png