跳转至

打砖块⚓︎

Leetcode题目链接

描述⚓︎

详见中文题目链接。

解答⚓︎

 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
class Solution {
private:
    int m, n;

    // start from (x, y), meet 1 => infect into 2
    // return the number of newly added 2s
    int dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1)
            return 0;
        grid[x][y] = 2;
        return 1 + dfs(grid, x + 1, y) + dfs(grid, x, y + 1) + dfs(grid, x - 1, y) + dfs(grid, x, y- 1);
    }

    bool worth(vector<vector<int>>& grid, int i, int j) {
        if (grid[i][j] != 1) return false;
        if (i == 0) return true;
        return (i > 0 && grid[i - 1][j] == 2) || (i < m - 1 && grid[i + 1][j] == 2) || (j > 0 && grid[i][j - 1] == 2) || (j < n - 1 && grid[i][j + 1] == 2);
    }

public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        m = grid.size(); n = grid[0].size();
        vector<int> res(hits.size(), 0);
        if (m == 1) return res;

        for (auto hit : hits) {
            grid[hit[0]][hit[1]]--;
        }

        for (int i = 0; i < n; i++) {
            dfs(grid, 0, i);
        }

        int row, col;
        for (int i = hits.size() - 1; i >= 0; i--) {
            row = hits[i][0]; col = hits[i][1];
            grid[row][col]++;
            if (worth(grid, row, col)) {
                res[i] = dfs(grid, row, col) - 1;
            }
        }

        return res;
    }
};