题目描述

我们有一组包含 1 和 0 的网格；其中 1 表示砖块。当且仅当一块砖直接连接到网格的顶部，或者它至少有一块相邻（4 个方向之一）砖块不会掉落时，它才不会落下。

我们会依次消除一些砖块。每当我们消除 (i, j) 位置时， 对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这个消除而落下。

返回一个数组表示每次消除操作对应落下的砖块数目。

样例

输入：
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
输出: [2]
解释: 
如果我们消除 (1, 0) 位置的砖块, 在 (1, 1) 和 (1, 2) 的砖块会落下。
所以我们应该返回 2。

输入：
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
输出：[0,0]
解释：
当我们消除 (1, 0) 的砖块时，(1, 1) 的砖块已经由于上一步消除而消失了。
所以每次消除操作不会造成砖块落下。注意 (1, 0) 砖块不会记作落下的砖块。

提示

• 网格的行数和列数的范围是 [1, 200]。
• 消除的数字不会超过网格的区域。
• 可以保证每次的消除都不相同，并且位于网格的内部。
• 一个消除的位置可能没有砖块，如果这样的话，就不会有砖块落下。

算法

(时光倒流 + 宽度优先遍历) $O(nm + Q)$

1. 按照正常的想法，每消除一个位置，都需要重新开始宽度优先遍历统计目前剩余的砖块的数量。这样做每次操作的时间复杂度就是 $O(nm)$，会超时。
2. 考虑时光倒流，我们一开始将所有待消除的位置上的砖块都进行消除（如果这个位置本来没有砖块则直接记录答案为 0），然后按相反的顺序往回添加。
3. 首先，在往回添加前，做一次宽度优先遍历统计目前剩余砖块的情况。这里我们假设能留住的砖块记为 1，会掉落但没被消除的砖块记为 2，其余位置为 0（包括被消除的位置）。
4. 考虑添加一个砖块，如果这个砖块的四个方向有为 1 的位置（或者与顶部相连），则表明原来的消除会导致一些位置砖块的掉落，所以从当前位置开始进行宽度优先遍历。注意，这里只遍历值为 2 的位置，将这些 2 的位置改为 1。发生改变的位置的数量就是原来消除的答案。
5. 如果这个新添加的砖块四个方向没有为 1 的位置，则表明在原来的消除过程中，这个位置已经在更早的消除中掉落，这个位置的值更新为 2，答案为 0。

时间复杂度

• 每个位置最多被遍历常数次，即变为 1 的位置不会再变回 2 或 0。宽搜的过程也不会再去访问不为 2 的位置，每个 2 的位置仅会被访问一次。
• 故总时间复杂度为 $O(nm + Q)$。

空间复杂度

• 需要额外 $O(nm + Q)$ 的空间维护队列和保存答案。

C++ 代码

class Solution {
public:
    int bfs(vector<vector<int>> &grid, const vector<pair<int, int>> &S) {
        int n = grid.size(), m = grid[0].size();
        const int dx[4] = {0, 1, 0, -1};
        const int dy[4] = {1, 0, -1, 0};

        queue<pair<int, int>> q;
        for (const auto &s : S)
            q.push(s);

        int cnt = 0;

        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = u.first + dx[i], y = u.second + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 2)
                    continue;

                grid[x][y] = 1;
                q.push(make_pair(x, y));
                cnt++;
            }
        }

        return cnt;
    }

    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int n = grid.size(), m = grid[0].size(), h = hits.size();
        vector<int> ans(h);

        for (int i = h - 1; i >= 0; i--)
            if (grid[hits[i][0]][hits[i][1]] == 0) {
                ans[i] = 0;
            } else {
                ans[i] = -1;
                grid[hits[i][0]][hits[i][1]] = 0;
            }

        for (int i = 1; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 1)
                    grid[i][j] = 2;

        vector<pair<int, int>> S;
        for (int j = 0; j < m; j++)
            if (grid[0][j] == 1)
                S.emplace_back(0, j);

        bfs(grid, S);

        for (int i = h - 1; i >= 0; i--) {
            if (ans[i] == 0)
                continue;

            int x = hits[i][0], y = hits[i][1];

            if (x == 0
             || grid[x - 1][y] == 1
             || x < n - 1 && grid[x + 1][y] == 1
             || y > 0 && grid[x][y - 1] == 1
             || y < m - 1 && grid[x][y + 1] == 1) {
                grid[x][y] = 1;
                ans[i] = bfs(grid, {make_pair(x, y)});
            } else {
                grid[x][y] = 2;
                ans[i] = 0;
            }
        }

        return ans;
    }
};