题目描述

We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.

We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.

Return an array representing the number of bricks that will drop after each erasure in sequence.

Example 1:
Input: 
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation: 
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.
Example 2:
Input: 
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation: 
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping.  Note that the erased brick (1, 0) will not be counted as a dropped brick.

Note:

• The number of rows and columns in the grid will be in the range [1, 200].
• The number of erasures will not exceed the area of the grid.
• It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.
• An erasure may refer to a location with no brick - if it does, no bricks drop.

题意：我们有一组包含1和0的网格；其中1表示砖块。 当且仅当一块砖直接连接到网格的顶部，或者它至少有一块相邻（4 个方向之一）砖块不会掉落时，它才不会落下。我们会依次消除一些砖块。每当我们消除(i, j) 位置时， 对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这个消除而落下。返回一个数组表示每次消除操作对应落下的砖块数目。

算法1

(并查集)

题解：首先我们将所有的击倒位置的砖块去掉（从1变成-1），剩下的那些与第一行连通的砖块肯定是不会最终掉落下来的。所以非常直观的想法就是每次打掉一个砖块之后，从顶部进行一遍BFS，求当前连通块大小和上一个连通块大小的差值，但是这样做的话，会超时。

考虑到是连通分量的问题，我们尝试使用并查集来解决，但是并查集解决的问题是查找与合并，但是这个问题确实不断的将连通分量分割开，这并不是朴素并查集的能力范围。但是我们如果把问题倒过来考虑，我们先把所有的击倒的砖块去掉，剩下的那些砖块，我们进行合并。然后，我们逆序将打掉砖块一个个的添上去，这样就是不断的合并操作了！！！如果能考虑到这里，问题似乎变得可以解决了。算法如下：

• 首先将所有打掉砖块的位置，从1变成-1。如果原来位置没有砖块或者重复打掉，不需要处理。
• 然后我们将剩下的砖块进行合并，这里我们使用了一个小trick，我们将与cnt节点在一个集合中的节点代表最后能留下的节点。我们从上到下，从左到右进行合并。这时候size[getfa(cnt)]就是最后剩下来的节点个数。
• 我们尝试从最后一个击打位置进行复原砖块，同时将该砖块与上下左右四个位置的砖块进行合并操作。
• 我们判断当前复原的砖块是不是在最终留下来的砖块连通分量中（getfa(idx) == getfa(cnt) ?），如果是的话，说明我们这次复原砖块可以增加最终剩下来砖块，还原到原问题中就是这次打碎砖块使得若干个砖块掉落了。

C++ 代码

class Solution{
public:
    vector<int> fa,size;
    int n,m,l,cnt,dx[4] = {0,-1,0,1},dy[4] = {-1,0,1,0};
    int getfa(int x)
    {
        if(x != fa[x]) fa[x] = getfa(fa[x]);
        return fa[x];
    }
    void uni(int x,int y)
    {
        int fx = getfa(x),fy = getfa(y);
        if(fx != fy)
        {
            if(size[fx] < size[fy])
            {
                fa[fx] = fy;
                size[fy] += size[fx];
            }else{
                fa[fy] = fx;
                size[fx] += size[fy];
            }
        }
    }
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        n = grid.size(),m = grid[0].size(),cnt = n * m,l = hits.size();
        fa = vector<int>(cnt + 1,0),size = vector(cnt + 1,1);
        vector<int> res(l,0);
        for(int i = 0 ; i <= cnt ; i ++) fa[i] = i;
        for(vector<int> hit:hits)
            if(grid[hit[0]][hit[1]] == 1)
                grid[hit[0]][hit[1]] = -1;
        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < m ; j ++)
            {
                int idx = i * m + j;
                if(grid[i][j] == 1)
                {
                    if(i == 0) uni(idx,cnt);
                    if(i > 0 && grid[i - 1][j] == 1) uni(idx,(i - 1) * m + j);
                    if(j > 0 && grid[i][j - 1] == 1) uni(idx,i * m + (j - 1)); 
                }
            }
        }
        for(int i = l - 1; i >= 0 ;i --)
        {
            int x = hits[i][0],y = hits[i][1];
            if(grid[x][y] == -1)
            {
                int pre = size[getfa(cnt)],idx = x * m + y;
                grid[x][y] = 1;
                if(x > 0 && grid[x - 1][y] == 1) uni((x - 1) * m + y,idx);
                if(x < n - 1 && grid[x + 1][y] == 1) uni((x + 1) * m + y,idx);
                if(y > 0 && grid[x][y - 1] == 1) uni(x * m + y - 1,idx);
                if(y < m - 1 && grid[x][y + 1] == 1) uni(x * m + y + 1,idx);
                if(x == 0) uni(cnt,idx);
                int after = size[getfa(cnt)],root = getfa(cnt),cur = getfa(idx);
                if(root == cur) res[i] = after - pre - 1;
            }
        }
        return res;
    }
};