思路
比较经典的Flood Fill 算法
C++ 代码
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
bool vis[105][105];
bool map[105][105];
void dfs(int x, int y, int R, int C)
{
int a,b;
vis[x][y] = 1;
for(int i = 0; i<4; i++){
a = x + dx[i], b = y + dy[i];
if(a>=0 && a<R && b>=0 && b<C && !vis[a][b] && map[a][b]){
dfs(a,b,R,C);
}
}
}
int query(int R, int C)
{
int res = 0;
for(int i = 0; i<R; i++){
for(int j = 0; j<C; j++){
if(!vis[i][j] && map[i][j]){
dfs(i,j,R,C);
res++;
}
}
}
return res;
}
int main()
{
int T,R,C,x,y,z,N, count;
char op;
vector<int> ans;
cin>>T;
for(int num = 1; num<=T; num++)
{
count = 0;
cin>>R>>C;
for(int i = 0; i<R; i++){
string row;
cin>>row;
for(int j = 0; j<C; j++){
map[i][j] = row[j] - '0';
}
}
cin>>N;
while(N--){
cin>>op;
memset(vis,0,sizeof(vis));
if(op == 'Q'){
ans.push_back(query(R, C));
count++;
}
else {
cin>>x>>y>>z;
map[x][y]= z;
}
}
cout<<"Case #"<<num<<":"<<endl;
for(int i = 0; i<count; i++) cout<<ans[i]<<endl;
ans.clear();
}
return 0;
}