AOJ 0118 Property Distribution 题解

题意大概就是判断区域的个数,同样的字符属于一个区域,问有多少个区域.

想起来以前一位老师给我讲的一道类似的题目...直接DFS求解,已经判断过的区域再用另一个字符填上即可.

#include<cstdio>
#include<iostream>

using namespace std;

char tmap[1000][1000];

int w,h;

int ans;

int dfs(int x,int y,char seed){
	if(x<0 || x>w || y>h || y<0) return 0;
	if(tmap[x][y]==0 ||seed != tmap[x][y]) return 0;
	tmap[x][y] = 0;
			dfs(x,y-1,seed);
		dfs(x-1,y,seed);dfs(x+1,y,seed);
			dfs(x,y+1,seed);
	
	return 1;
}

int main(void){
	while(1){
	cin>>w>>h;
	if(h==0 && w==0) break;
	for(int i = 1;i<=w;i++){
		for(int j = 1;j<=h;j++){
			cin>>tmap[i][j];
		}
	}
	
	for(int i = 1;i<=w;i++){
		for(int j = 1;j<=h;j++){
			char seed = tmap[i][j];
			if(dfs(i,j,seed)==1) ans++;
		}
	}
	
	cout<<ans<<endl;
	ans = 0;
	}
	return 0;
}