多源+多次BFS：着火的房间

拼搏现实的明天。 2023-10-06 19:36 157阅读 0赞

## 多源+多次BFS：着火的房间 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

问题看似很麻烦，在移动的同时起火的位置也在变化。但可发现对于每个将要起火的点，它的起火时间都是可确定的， 当我们确定了所有将要起火的点的起火时间，问题就变成了普通的bfs问题（使用了预处理的思想）。  
  bfs入队的节点包括坐标属性x,y，以及时间time。  
  我们可以进行两次bfs，第一次bfs为多源bfs，将初始的起火点入队，进行bfs获得所有将要起火点的起火时间，用二维数组fireTime\[\] \[\]保存。第二次bfs为普通bfs，进行移动。  
  根据多源bfs的特性，将初始所有起火点入队后进行bfs，得到的将要起火点的起火时间为最早被扩散起火的时间（因为每个点都是由距其最近的起火点扩散而来的，此为多源bfs的重要特性）。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]

**需注意的点：**

*  保存每个点起火时间fireTime\[\] \[\]的初始值要设为无穷大，对于不起火的点，无穷大则表示不会起火。初值不能设为-1，判断不能移动到某点时的条件之一为将要移动的点的起火时间小于等于当前时间 + 1，若输入矩阵没有起火点，初值不会刷新，则会造成判断错误。

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static int[][] visit = new int[102][102];
        static int[][] fireTime = new int[102][102];
        static LinkedList<Node> q = new LinkedList<>();
        static int[][] dirF = {
        {
        1, 0}, {
        -1, 0}, {
        0, 1}, {
        0, -1}, {
        -1, -1},
                {
        -1, 1}, {
        1, -1}, {
        1, 1}};
        static int[][] dir = {
        {
        1, 0}, {
        -1, 0}, {
        0, 1}, {
        0, -1}};
        static final int INF = Integer.MAX_VALUE;
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n, m, k, i, j;
            Node start = null;
            Node end = null;
            StringBuilder s = new StringBuilder();
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                m = scanner.nextInt();
                k = scanner.nextInt();
                if (n + m + k == 0) {
        
                    return;
                }
                for (i = 0;i < n;i++) {
        
                    s.delete(0, s.length());
                    s.append(scanner.next());
                    for (j = 0;j < s.length();j++) {
        
                        visit[i][j] = 0;
                        if (s.charAt(j) == 'f') {
        
                            fireTime[i][j] = 0;
                            q.add(new Node(i, j, 0));
                        } else if (s.charAt(j) == 't') {
        
                            end = new Node(i, j, 0);
                            fireTime[i][j] = INF;
                        } else {
        
                            if (s.charAt(j) == 's') {
        
                                start = new Node(i, j, 0);
                                visit[i][j] = 1;
                            }
                            fireTime[i][j] = INF;
                        }
                    }
                }
                getFireTime(k, n, m);
                q.add(start);
                if (!bfs(n, m, end)) {
        
                    System.out.println("Impossible");
                }
            }
    
        }
    
        static void getFireTime(int k, int n, int m) {
        
            Node fNow;
            int i, xx, yy;
            while (!q.isEmpty()) {
        
                fNow = q.pop();
                for (i = 0;i < 8;i++) {
        
                    xx = fNow.x + dirF[i][0];
                    yy = fNow.y + dirF[i][1];
                    if (xx < 0 || xx >= n || yy < 0 || yy >= m ||
                            fireTime[xx][yy] != INF) {
        
                        continue;
                    }
                    fireTime[xx][yy] = fNow.time + k;
                    q.add(new Node(xx, yy, fireTime[xx][yy]));
                }
            }
        }
    
        static boolean bfs(int n, int m, Node end) {
        
            Node now;
            int i, xx, yy;
            while (!q.isEmpty()) {
        
                now = q.pop();
                for (i = 0;i < 4;i++) {
        
                    xx = now.x + dir[i][0];
                    yy = now.y + dir[i][1];
                    if (xx < 0 || xx >= n || yy < 0 || yy >= m ||
                            visit[xx][yy] == 1 || fireTime[xx][yy] <= now.time + 1) {
        
                        continue;
                    }
                    if (xx == end.x && yy == end.y) {
        
                        System.out.println(now.time + 1);
                        while (!q.isEmpty()) {
        
                            q.pop();
                        }
                        return true;
                    }
                    visit[xx][yy] = 1;
                    q.add(new Node(xx, yy, now.time + 1));
                }
            }
            return false;
        }
    
    }
    
    class Node {
        
        public int x;
        public int y;
        public int time;
    
        public Node(int x, int y, int time) {
        
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6ad95524fba643fe8c35ce7ead5f73b0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/fe089b9da8d54cdc926549d81386a18b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/03f3adccff11409d8de905ce1ba7f717.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16