Property Distribution
タナカ氏が HW アールの果樹園を残して亡くなりました。果樹園は東西南北方向に H×W の区画に分けられ、区画ごとにリンゴ、カキ、ミカンが植えられています。タナカ氏はこんな遺言を残していました。
果樹園は区画単位でできるだけ多くの血縁者に分けること。ただし、ある区画の東西南北どれかの方向にとなりあう区画に同じ種類の果物が植えられていた場合は、区画の境界が分からないのでそれらは 1 つの大きな区画として扱うこと。
例えば次のような 3x10 の区画であれば(リはリンゴ、カはカキ、ミはミカンを表す)
同じ樹がある区画の間の境界を消すと次のようになり、
結局 10 個の区画、つまり 10 人で分けられることになります。 雪が降って区画の境界が見えなくなる前に分配を終えなくてはなりません。あなたの仕事は果樹園の地図をもとに分配する区画の数を決めることです。ということで、果樹園の地図を読み込み、分配を受けられる血縁者の人数を出力して終了するプログラムを作成してください。ただし、果樹園の地図は W 文字×H 行の文字列として与えられます。この文字列には、リンゴを表す@、カキを表す#、ミカンを表す*、の 3 文字しか使われていません。
Input
複数のデータセットが与えられます。各データセットは空白で区切られたH Wを含む行から始まり、続いてH × Wの文字が与えられます。入力はゼロが２つの行で終わります。
H, W は100以下です。
Output
各データセットごとに、分配を受ける人数を１行に出力してください。
Sample Input
10 10 ####*****@ @#@@@@#*#* @##***@@@* #****#*@** ##@*#@@*## *@@@@*@@@# ***#@*@##* *@@@*@@##@ *@*#*@##** @****#@@#@ 0 0
Output for the Sample Input
33 很典型的DFS题，难度不高，很适合练练手。 以下给出AC代码： 翻译网上有很多，这里不再复述。#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<string> #include<vector> #define rep(i,a,n) for(int i=a;i<n;i++) #define per(i,n,a) for(int i=n;i>a;i--) #define mem0(x) memset(x,0,sizeof(x)) #define memff(x) memset(x,INF,sizeof(x)) #define INF 100000000 using namespace std; typedef pair<int,int> p; typedef long long LL; int h,w; int nh,nw; int dw[4]={0,1,0,-1},dh[4]={1,0,-1,0}; int cal; char maze[105][105]; void DFS_1(int sh,int sw) {maze[sh][sw]='.';for(int i=0;i<4;i++){nh=sh+dh[i];nw=sw+dw[i];if(1<=nh&&nh<=h&&1<=nw&&nw<=w&&maze[nh][nw]=='#'){DFS_1(nh,nw);}} } void DFS_2(int sh,int sw) {maze[sh][sw]='.';for(int i=0;i<4;i++){nh=sh+dh[i];nw=sw+dw[i];if(1<=nh&&nh<=h&&1<=nw&&nw<=w&&maze[nh][nw]=='*'){DFS_2(nh,nw);}} } void DFS_3(int sh,int sw) {maze[sh][sw]='.';for(int i=0;i<4;i++){nh=sh+dh[i];nw=sw+dw[i];if(1<=nh&&nh<=h&&1<=nw&&nw<=w&&maze[nh][nw]=='@'){DFS_3(nh,nw);}} } int main() {//freopen("input.in","r",stdin);while(cin>>h>>w){if(h==0&&w==0)break;cal=0;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++)cin>>maze[i][j];}for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){if(maze[i][j]=='#'){DFS_1(i,j);cal++;}}}for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){if(maze[i][j]=='*'){DFS_2(i,j);cal++;}}}for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){if(maze[i][j]=='@'){DFS_3(i,j);cal++;}}}cout<<cal<<endl;}return 0; }