紫书第六章的题,用并查集重写一遍,果然还是书上给的dfs方法更简单……
一开始用fa[i*m+j] != i*m+j 来判断是否访问过,虽然没想出来为什么WA,但是确实不如用vis稳
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int fa[],m,n,cnt,vis[][];
char mp[][];
int find(int x){return fa[x] == x?x:fa[x] = find(fa[x]);}
void merge(int x,int y){
int fx = find(x);
int fy = find(y);
if(fx == fy) return ;
fa[fx] = fy;
}
void dfs(int x,int y,int fx,int fy){
if(x< || x>=m || y< || y>=n) return;
if(vis[x][y] || mp[x][y] == '*') return;
vis[x][y] = ;
//cout<<"x || y || fx || fy : "<<x<<" || "<<y<<" || "<<fx<<" || "<<fy<<endl;
if(fx != -) merge(x*m+y,fx*m+fy);
for(int i = -;i<;i++){
for(int j = -;j<;j++){
if(!i && !j) continue;
dfs(x+i,y+j,x,y);
}
}
}
int main(){
while(scanf("%d%d",&m,&n) == && m && n){
cnt = ;
memset(vis,,sizeof(vis));
for(int i = ;i<m;i++) scanf("%s",mp[i]);
for(int i = ;i<;i++) fa[i] = i;
for(int i = ;i<m;i++)
for(int j = ;j<n;j++)
if(!vis[i][j] && mp[i][j] == '@') dfs(i,j,-,-),cnt++;
printf("%d\n",cnt);
}
return ;
}