AcWing 643. 动态网格
原题链接
简单
作者:
木可柯
,
2024-03-29 15:45:21
,
所有人可见
,
阅读 4
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int r, c;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
bool vis[N][N];
char g[N][N];
//找上下左右联通的,上下左右能联通的话就是一个连通块全部赋值为false
void dfs(int x, int y)
{
vis[x][y] = true;
for(int i = 0; i < 4; i++)
{
int ax = x + dir[i][0], bx = y + dir[i][1];
if(ax < 0 || ax >= r || bx < 0 || bx >= c || g[ax][bx] != '1' || vis[ax][bx])
continue;
dfs(ax, bx);
}
}
int main()
{
int n, i = 1;
cin >> n;
while(i <= n) {
cin >> r >> c;
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
cin >> g[i][j];
int t;
cin >> t;
printf("Case #%d:\n", i);
while(t--) {
char cp[2];
scanf("%s", cp);
if(cp[0] == 'Q') {
memset(vis, false, sizeof vis);
int res = 0;
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
//当前为一个联通块
if(g[i][j] == '1' && !vis[i][j])
{
res++;
dfs(i, j);
}
}
}
cout << res << endl;
} else {
int x, y, z;
cin >> x >> y >> z ;
g[x][y] = z + '0';
}
}
i++;
}
return 0;
}