题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=513

简单的dfs应用,算是加深了对dfs的理解!

code:

#include <stdio.h>
#include <string.h>
#define MAX 102
int m,n,sum;
char map[MAX][MAX],flag[MAX][MAX];
void dif(int i,int j)
{
if(map[i][j]!=’@’||flag[i][j]==’1’||i<0||i>=m||j<0&&j>=n)
return ;
else
{
if(map[i][j]==’@’)
{
flag[i][j]=’1′;
dif(i,j-1);
dif(i-1,j-1);
dif(i-1,j);
dif(i-1,j+1);
dif(i,j+1);
dif(i+1,j+1);
dif(i+1,j+1);
dif(i+1,j);
dif(i+1,j-1);
}
}
}
int main()
{
while(scanf(“%d%d”,&m,&n),m&&n)
{
int i,j;
memset(map,0,sizeof(map));
memset(flag,0,sizeof(flag));
getchar();
sum=0;
for(i=0;i<m;i++)
gets(map[i]);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(map[i][j]==’@’&&flag[i][j]!=’1′)
{
sum++;
dif(i,j);
}
printf(“%d\n”,sum);
}
return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation