【暑假复习】【搜索】AOJ0118:Property Distribution

题意

有三种符号，同种符号四联通，求连通块总数

题解

枚举每一个点，若未被访问过，就访问这个点所在的连通块，将整个连通块的点全部标记，总数++

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 110
using  namespace std;
int w[4][2]={
   {
   1,0},{
   0,-1},{-1,0},{
   0,1}};
int col[MAXN][MAXN],vis[MAXN][MAXN],n,m,cnt;
char c;
bool check(int x,int y){if(x*y==0||x>n||y>m)return 0;if(vis[x][y]==1)return 0;return 1;
}
void dfs(int x,int y){vis[x][y]=1;for(int i=0;i<4;i++){int x1=x+w[i][0];int y1=y+w[i][1];if(check(x1,y1)&&col[x1][y1]==col[x][y])dfs(x1,y1);}
}
int main(){SF("%d%d",&n,&m);while(n*m!=0){memset(col,0,sizeof col);memset(vis,0,sizeof vis);cnt=0;for(int i=1;i<=n;i++){SF("\n");for(int j=1;j<=m;j++){SF("%c",&c);if(c=='@')col[i][j]=1;else if(c=='#')col[i][j]=2;elsecol[i][j]=3;}}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(vis[i][j]==0){cnt++;dfs(i,j);}PF("%d\n",cnt);SF("%d%d",&n,&m);}
}