題目大意：給出水管的分布，求出需要多少個水源。即求出無向圖有多少個連通分量。
DFS遍歷一次即可。
以下是我的代碼：
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(57);
const int kWater[]={6,10,20,24,18,12,14,22,28,26,30};
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int m,n;
char g[kMaxn][kMaxn];
bool used[kMaxn][kMaxn];
void dfs(int x,int y)
{
used[x][y]=true;
for(int i=0;i<4;i++)
{
int xx(x+dx[i]),yy(y+dy[i]);
if(xx<1 || xx>m || yy<1 || yy>n || used[xx][yy])
continue;
int t1(g[x][y]-'A'),t2(g[xx][yy]-'A');
if(i==0 && (kWater[t1]&(1<<3)) && (kWater[t2]&(1<<2)))
dfs(xx,yy);
else if(i==1 && (kWater[t1]&(1<<2)) && (kWater[t2]&(1<<3)))
dfs(xx,yy);
else if(i==2 && (kWater[t1]&(1<<4)) && (kWater[t2]&(1<<1)))
dfs(xx,yy);
else if(i==3 && (kWater[t1]&(1<<1)) && (kWater[t2]&(1<<4)))
dfs(xx,yy);
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%d%d",&m,&n)==2 && m>=0 && n>=0)
{
for(int i=1;i<=m;i++)
{
getchar();
for(int j=1;j<=n;j++)
scanf("%c",&g[i][j]);
}
int ans(0);
memset(used,false,kMaxn*kMaxn*sizeof(bool));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(!used[i][j])
{
ans++;
dfs(i,j);
}
printf("%d\n",ans);
}
return 0;
}
posted on 2011-05-26 15:38
lee1r 閱讀(205)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論