假设我们有一个二进制值（0和1）的网格，单元格中的1代表砖。满足以下条件的砖不会掉落-
任一砖都直接连接到网格顶部
或至少相邻的一块砖（顶部，底部，左侧，右侧）不会掉落。
我们将按顺序进行一些擦除。在每种情况下，我们都希望在位置(i,j)处进行擦除，该位置上的砖块（如果存在）将消失，然后由于该擦除操作，其他一些砖块可能会掉落。我们必须找到一个数组，该数组表示每次擦除后将下降的砖块数量。
因此，如果输入像grid = [[1,0,0,0]，[1,1,1,0]]并命中= [[1,0]]，那么输出将是[2]，这是因为如果我们移除放置在(1,0)处的砖，则(1,1)和(1,2)处的砖将掉落。所以我们应该返回2。
为了解决这个问题，我们将遵循以下步骤-
定义大小为4 x 2的数组dir，dir：= {{{1，0}，{-1，0}，{0，1}，{0，-1}}
定义一个函数dfs()，它将使用i，j，网格，
如果(i,j)在网格区域内并且grid [i，j]不等于1，则-
返回0
ret：= 1
格[i，j]：= 2
对于初始化k：= 0，当k <4时，更新（将k增加1），执行-
ret：= ret + dfs（i + dir [k，0]，j + dir [k，1]，网格）
返回ret
定义一个函数notConnected()，它将采用x，y和网格，
对于初始化k：= 0，当k <4时，更新（将k增加1），执行-
返回真
忽略以下部分，跳至下一个迭代
nx：= x + dir [k，0]，ny：= y + dir [k，1]
如果(nx,ny)在网格范围内，则-
如果grid [nx，ny]与2相同，则-
当x等于0时返回true
从主要方法中，执行以下操作-
定义数组ret
对于初始化i：= 0，当i <命中大小时，更新（将i增加1），执行-
grid [hits [i，0]，hits [i，1]]：= grid [hits [i，0]，hits [i，1]]-1
对于初始化i：= 0，当i <网格大小时，更新（将i增加1），执行-
dfs（0，i，格）
反转阵列命中
对于初始化i：= 0，当i <命中大小时，更新（将i增加1），执行-
在ret的末尾插入0
在ret的末尾插入dfs(x,y,grid)
x：= hits [i，0]，y：= hits [i，1]
如果grid [x，y]等于1且notConnected(x,y,grid)，则-
除此以外
反转数组ret
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
int dfs(int i, int j, vector<vector<int> >& grid){
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) {
return 0;
}
int ret = 1;
grid[i][j] = 2;
for (int k = 0; k < 4; k++) {
ret += dfs(i + dir[k][0], j + dir[k][1], grid);
}
return ret;
}
bool notConnected(int x, int y, vector<vector<int> >& grid){
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid[0].size())
continue;
if (grid[nx][ny] == 2) {
return true;
}
}
return x == 0;
}
vector<int> hitBricks(vector<vector<int> >& grid, vector<vector<int> >& hits){
vector<int> ret;
for (int i = 0; i < hits.size(); i++) {
grid[hits[i][0]][hits[i][1]] -= 1;
}
for (int i = 0; i < grid.size(); i++) {
dfs(0, i, grid);
}
reverse(hits.begin(), hits.end());
for (int i = 0; i < hits.size(); i++) {
int x = hits[i][0];
int y = hits[i][1];
grid[x][y] += 1;
if (grid[x][y] == 1 && notConnected(x, y, grid))
ret.push_back(dfs(x, y, grid) - 1);
else
ret.push_back(0);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{1,1,1,0}};
vector<vector<int>> v1 ={{1,0}};
print_vector(ob.hitBricks(v, v1));
}{{1,0,0,0},{1,1,1,0}}, {{1,0}}输出结果
[2, ]