分析
本题可以采用并查集,也可以用dfs方法解决。
首先将所有不会掉落的砖块放入集合se中。
然后将每次击打的坐标砖块的周围四个方位进行dfs,看看有没有砖块可以加入到不会掉落的集合se中。
加入之后集合se的大小的前后差值就是打掉一个砖块的答案。
C++ 代码
class Solution {
public:
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(vector<vector<int>>& grid,int x,int y,unordered_set<int>& se)
{
int n=grid.size(),m=grid[0].size();
if (x<0 || x>=n || y<0 || y>=m || grid[x][y] != 1 || se.count(x*m+y)) return;
se.insert(x*m+y); //该砖块满足条件,加入到集合中
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
dfs(grid,xx,yy,se);
}
}
vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
int n=grid.size(),m=grid[0].size();
vector<int> ans(hits.size());
unordered_set<int> se;
for(int i=0;i<hits.size();i++)
grid[hits[i][0]][hits[i][1]]-=1;
for(int i=0;i<m;i++)
{
if (grid[0][i]==1)
dfs(grid,0,i,se); //将所有不会掉落砖块加入到集合中,最顶上的砖块dfs
}
for (int i=hits.size()-1;i>=0;i--) {
int temp=se.size(); //进行dfs前的集合大小
auto x=hits[i][0],y=hits[i][1];
if(++grid[x][y]!=1) continue;
if((x-1>=0 && se.count((x-1)*m+y)) || (x+1<n && se.count((x+1)*m+y))
|| (y-1>=0 && se.count(x*m+y-1)|| (y+1<m && se.count(x*m+y+1)) || x==0))
{
dfs(grid,x,y,se); //以上条件有一个满足就把砖块加入到集合中
ans[i]=se.size()-temp-1; //目前集合大小-temp-1
}
}
return ans;
}
};