DFS搜索 hdu1241

比如：题目说的是在一个矩阵里，有些格子是矿井，有些不是，相邻（上、下、左、右、左上、右上、左下、右下）的格子如果也是矿井，那么他们属于同一个矿井，问总共有多少个矿井。很明显就是DFS。

1 1 * 3 5 *@*@* **@** *@*@* 1 8 @@****@* 5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ 0 0

思路：

    DFS型。分别以每个点为起点扫描一次，判断连通分量个数即可。

#include<stdio.h>
/**
** 深度搜索一般用递归
**/
#define Maxn 150
char s[Maxn][Maxn];//用二维数组存储图结构
int move[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};//定义八个可行方向
int m,n,k,ans;
void dfs(int x,int y)
{
   int i;
   for(i=0;i<8;i++)//依次扫描八个方向,寻找可行点
   {
      int tx=x+move[i][0];
      int ty=y+move[i][1];
      if(tx>=0&&tx<m&&ty>=0&&ty<n&&s[tx][ty]=='@')//判断是否超出地图边界和是否可行
      {
         s[tx][ty]='*';//标记已经走过的点
         dfs(tx,ty);//以此点为起点继续深入搜索,这就是深度优先搜索
      }
   }
}
int main()
{
   int i,j;
   while(scanf("%d%d",&m,&n))
   {
      ans=0;
      if(m==0&&n==0) break;
      for(i=0;i<m;i++)
      {
         scanf("%s",s[i]);
      }
      for(i=0;i<m;i++)//分别以每个点为起点扫描一次，判断连通分量个数即可。
      {
         for(j=0;j<n;j++)
         {
            if(s[i][j]=='@')//直接忽略没有油田的点
            {
               s[i][j]='*';//标记该点已经走过
               ans++;
               dfs(i,j);
            }
         }
      }
      printf("%d\n",ans);
   }
   return 0;
}