圖的連通性問題，我用的是dfs，如果bfs的話需要建隊列，比較麻煩，也沒有必要。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
const long maxn=108;
long m,n,ans,xd[]={-1,-1,0,1,1,1,0,-1},yd[]={0,1,1,1,0,-1,-1,-1};
char a[maxn][maxn];
bool used[maxn][maxn];
void dfs(long x,long y)
{
used[x][y]=true;
for(long k=0;k<8;k++)
{
long xx=x+xd[k],yy=y+yd[k];
if(xx>=1&&xx<=m&&yy>=1&&yy<=n&&!used[xx][yy]&&a[xx][yy]=='@')
dfs(xx,yy);
}
}
int main()
{
/*
freopen("program.in","r",stdin);
freopen("program.out","w",stdout);
//*/
while(scanf("%ld%ld",&m,&n)==2)
{
if(m==0||n==0) return 0;
getchar();
memset(a,0,sizeof(a));
memset(used,false,sizeof(used));
// Clear
for(long i=1;i<=m;i++)
{
for(long j=1;j<=n;j++)
scanf("%c",&a[i][j]);
getchar();
}
// Read In
ans=0;
for(long i=1;i<=m;i++)
for(long j=1;j<=n;j++)
if(!used[i][j]&&a[i][j]=='@')
{
dfs(i,j);
ans++;
}
printf("%ld\n",ans);
}
return 0;
}
posted on 2010-01-07 13:39
lee1r 閱讀(384)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論