AcWing 643. 动态网格
原题链接
简单
作者:
Lyle2021
,
2021-01-21 20:20:27
,
所有人可见
,
阅读 364
(BFS)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =110;
char g[N][N];
int h,w;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
void bfs(int sx,int sy){
if(sx<0||sx>=h||sy<0||sy>=w||g[sx][sy]=='0')return;
g[sx][sy]='0';
for(int i=0;i<4;i++){
int a=sx+dx[i],b=sy+dy[i];
bfs(a,b);
}
}
int main(){
int T,K;
cin>>T;
int t=T;
while(T--){
cin>>h>>w;
for(int i=0;i<h;i++)cin>>g[i];
cin>>K;
cout<<"Case #"<<t-T<<':'<<endl;
while(K--){
char E;
cin>>E;
if(E=='Q'){
int res=0;
char b[N][N];
memcpy(b,g,sizeof g);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(g[i][j]=='1'){
bfs(i,j);
res++;
}
}
}
memcpy(g,b,sizeof b);
cout<<res<<endl;
}
else if(E=='M'){
int mx,my;
char z;
cin>>mx>>my>>z;
g[mx][my]=z;
}
}
}
return 0;
}