BFS——练习题——蒜头君回家

题目.png

输入样例：

8 10
P.####.#P#
..#..#...#
..#T##.#.#
..........
..##.#####
..........
#####...##
###....S##

输出样例：

21

思路

---

最初的思路就是：找到第一把钥匙后立马找出口
利用三维数组，模拟两个平行面，在第一个平行面找到钥匙后，进入第二个平行面找出口。

利用BFS第一次找到的是最短这个特点，可以得知第一次找到钥匙是最短，第一次到出口也是最短，所以总路径最短。

代码

---

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

public class Main {
    
    static class Node {
        int x;
        int y;
        int step;       // 记录到这个点的步数
        int key = 0;    // 标记是否找到钥匙

        public Node(int x, int y, int step, int key) {
            super();
            this.x = x;
            this.y = y;
            this.step = step;
            this.key = key;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        int sx = 0;
        int sy = 0;

        char[][] map = new char[n][m];
        
        /**
         * 三维数组，第三维看作平行面，这里两个平行面
         *      在第一个平行面找钥匙，找到第一把钥匙就跳到第二平行面
         *      在第二个平行面找出口
         *      BFS是一层一层搜索的，所以找到第一把钥匙的步数要比第二把的短，
         *      拿到钥匙后，立马找出口，找的出口也是离这个钥匙是最短的
         */
        int[][][] vis = new int[n + 5][m + 5][2];
        
        int[][] dir = {
                {-1, 0},
                {0, 1},
                {1, 0},
                {0, -1}
        };
        
        for (int i = 0; i < n; i++) {
            String str = sc.next();
            for (int j = 0; j < m; j++) {
                char c = str.charAt(j);
                if(c == 'S') {
                    sx = i;
                    sy = j;
                }
                map[i][j] = str.charAt(j);
            }
        }
        
        Node start = new Node(sx, sy, 0, 0);
        
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(start);
        Node now = start;
        vis[sx][sy][0] = 1;
        
        while(!queue.isEmpty()) {
            now = queue.poll();
            int x = now.x;
            int y = now.y;
            int step = now.step;
            int key = now.key;
            
            // 找到第一把钥匙就进入第二平行面
            if(map[x][y] == 'P') {
                key = 1;
                vis[x][y][1] = 1;
            }
            
            // 拥有钥匙并找到出口就输出结果
            if(map[x][y] == 'T' && key == 1) {
                System.out.println(now.step);
                return;
            }
            
            for (int i = 0; i < 4; i++) {
                int tx = x + dir[i][0];
                int ty = y + dir[i][1];
                
                if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
                
                if(map[tx][ty] != '#' && vis[tx][ty][key] == 0) {
                    vis[tx][ty][key] = 1;
                    Node next = new Node(tx, ty, step + 1, key);
                    queue.add(next);
                }
            }
        }
    }
}