找出油田的數(shù)量 簡(jiǎn)單的dfs 搜索遍歷 入門題
http://acm.hdu.edu.cn/showproblem.php?pid=1241
#include <stdio.h>
#include <string.h>
#define N 110
int map[N][N];
int n,m,ans;
int visted[N][N];
void dfs( int x,int y)
{
if(map[x][y]==0 || visted[x][y] == 1)
return;
visted[x][y] = 1;
dfs(x-1,y-1);dfs(x-1,y);dfs(x-1,y+1);dfs(x,y+1);
dfs(x+1,y+1);dfs(x+1,y);dfs(x+1,y-1);dfs(x,y-1);
}
void Solve()
{
int i,j;
for(i = 1; i <=m;i++ )// map的邊界全是0
for(j = 1; j <=n; j ++)
if(map[i][j] == 1 && !visted[i][j])
ans++,dfs(i,j);
}
int main()
{
int i,j;
char str[N];
while(scanf("%d%d",&m,&n),m!=0||n!=0)
{
memset(map,0,sizeof(map));
memset(visted,0,sizeof(visted));
for(i = 0; i <m;i++ )
{
scanf("%s",str);
for(j = 0; j < n; j ++)
{
if(str[j]=='@') map[i+1][j+1] = 1;
}
}
ans = 0;
Solve();
printf("%d\n",ans);
}
return 0;
}
posted on 2010-05-18 13:16
付翔 閱讀(1219)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
ACM 數(shù)據(jù)結(jié)構(gòu)