Zombie in Matrix(BFS)

原文地址

给定一个二维矩阵， 值为1表示僵尸，0表示人类，每个僵尸每小时可以感染上下左右相邻的人类，求问多少小时后所有人类都被感染

非常标准的BFS题，一般的题面都是某一些特殊的元素（比如本题的僵尸）可以对相邻的（比如上下左右或九宫格）元素进行一定的操作（比如本题的所谓的感染）。

解题思路也很明确，数据结构使用队列

  1. 初始化。将最开始的所有特殊元素加入到队列中。

  2. 扩展队列。题目一般要求记录多少步完成“任务”，所以每一批扩展的元素不能混在一起加入队列。首先记录每一步扩展的个数，也即在扩展前队列的queue.size()，每一次扩展仅访问这么多的元素。

    取出队首并队首出队，找到该元素的所有满足题意的相邻元素（满足题意一般是1.没有越界 2.满足一定条件（比如本题的只有人才会被感染）），将这些元素入队，并且记录他们，以免重复访问

  3. 返回结果。当队列为空时表示无法扩展，那么如果已经完成题目要求的“任务”则返回步数，否则返回无法完成的标识（一般是-1）

本题代码：

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
public static int minHours(List<List<Integer>> grid) {
    Queue<int[]> queue = new LinkedList<>();
    int count = 0;
    int rows = grid.size();
    if (rows == 0) return -1;
    int columns = grid.get(0).size();
    if (columns == 0) return -1;
    for (int i=0; i<rows; ++i) {
        for (int j=0; j<columns; ++j) {
            if (grid.get(i).get(j) == 1) {
                queue.offer(new int[]{i, j});
                count++;
            }
        }
    }
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int min = 0;
    int target = rows * columns;
    while (true) {
        int len = queue.size();
        if (len == 0) break;
        if (count == target) return min;
        while (len > 0) {
            len--;
            int[] cur = queue.poll();
            for (int[] direction : directions) {
                int[] next = {cur[0] + direction[0], cur[1] + direction[1]};
                int x = next[0];
                int y = next[1];
                if (x >= 0 && x < rows && y >= 0 && y < columns && grid.get(x).get(y) == 0) {
                    count++;
                    grid.get(x).set(y, 1);
                    queue.offer(next);
                }
            }
        }
        min++;
    }
    return -1;
}

下面继续介绍两个典型的BFS题

Leetcode994 Rotting Oranges

原文地址

仍然是标准的BFS题，本题背景改为了腐烂的橙子，每个腐烂的橙子每分钟会让上下左右相邻的新鲜橙子腐烂，本题有个变化是存在空的单元格，但其实处理起来区别不大，只不过最后完成的任务不是所有格子都是腐烂的橙子，而是所有非空格子

本题代码

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
public int orangesRotting(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int target = n * m;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            if (grid[i][j] == 2) {
                queue.offer(new int[]{i, j});
            }
            else if(grid[i][j] == 0) {
                target--;
            }
        }
    }
    if (target == 0) return 0;
    int minute = 0;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty()) {
        int count = queue.size();
        target -= count;
        if (target == 0) return minute;
        for (int i=0; i<count; ++i) {
            int[] cur = queue.poll();
            for (int[] direction : directions) {
                int x = cur[0] + direction[0];
                int y = cur[1] + direction[1];
                if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                    queue.offer(new int[]{x, y});
                    grid[x][y] = 2;
                }
            }
        }
        minute++;
    }
    return -1;
}

Leetcode286 Walls and Gates

原文地址

本题在Leetcode上是付费题，可以在上面的Lintcode中看到题面

依然是BFS题，背景变为了求每个空房间到门的距离，与前两题不同的是，任务不是返回最后多少步，而是将每个步数填入访问的元素中

本题代码

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
public void wallsAndGates(int[][] rooms) {
    int n = rooms.length;
    int m = rooms[0].length;
    Queue<int[]> queue = new LinkedList<>();
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            if (rooms[i][j] == 0) {
                queue.offer(new int[]{i, j});
            }
        }
    }
    int distance = 1;
    final int INF = 2147483647;
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (true) {
        int cnt = queue.size();
        if (cnt == 0) break;
        while (cnt > 0) {
            cnt--;
            int[] cur = queue.poll();
            for (int[] direction : directions) {
                int[] next = {cur[0] + direction[0], cur[1] + direction[1]};
                int x = next[0];
                int y = next[1];
                if (x >= 0 && x < n && y >= 0 && y < m && rooms[x][y] == INF) {
                    rooms[x][y] = distance;
                    queue.offer(next);
                }
            }
        }
        distance++;
    }
}

Conclusion and points

  • 题面所要求的任务目标，可能是对矩阵本身做一些修改，比如第三题中，要将距离（扩展的步数）填入到矩阵中，或者大部分的直接返回将所有元素“覆盖”（感染、腐烂）的总步数
  • 扩展的新元素需要满足的条件，首要条件是不能越界。齐次是尚未“覆盖”的元素
  • 对于当前扩展的新元素，需要记录他们已经访问过，可以加入Set，或者直接修改其元素值当做标记
  • 其他点：取出队首同时队首要出队使用poll()即可；每一步扩展的元素是扩展前队列的大小；注意扩展方向是上下左右还是九宫格

最后更新： 2020年06月09日 21:57

原始链接： http://roooooobin.github.io/2020/06/07/Zombie-in-Matrix-BFS/

赏
× thanks~
打赏二维码