Oil Deposts(dfs)

思路

题意就是有一大片地方，让你去找里面有多少片油田(八个方向)，我们只需要遍历地图，当找到'@'的时候进行dfs，把搜索到的'@'都变成'*'就好了，然后用一个变量进行计数。

AC代码：

#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 105;
char MAP[MAXN][MAXN];
int dir[8][2] = {1,0, 0,1, -1,0, 0,-1, 1,1, -1,1, -1,-1, 1,-1};   // 因为有8个方向
int n,m;
int sum;

void dfs(int x,int y){
  MAP[x][y] = '*';                 // 把搜索到的油田标记成空地
  for(int i=0;i<8;i++){            // 8个方向搜索
    int X = x + dir[i][0];
    int Y = y + dir[i][1];
    if(X >= 0 && Y >= 0 && X < n && Y < m && MAP[X][Y] == '@'){
      dfs(X,Y);
    }
  }
  return ;
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
      if(n==0&&m==0) break;
      memset(MAP,0,sizeof(MAP));
      for(int i=0;i<n;i++){           // 给地图赋值
        scanf("%s",MAP[i]);
      }
      sum = 0;                        // sum记得清零
      for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
          if(MAP[i][j] == '@'){       // 遍历到油田时进行搜索
            dfs(i,j);
            sum++;                    // 计数
          }
        }
      }
      printf("%d\n",sum);
    }
    return 0;
}
/***
   [来源] UVa 572
   [题目] Oil Deposits
   [大意]
      经典的DFS题，这个就是求有多少片油田，只要8个方向连在一起的就是一片
      所以只需要遍历地图，当找到一个油田时进行搜索，把搜索到的油田都变成
      空地就好了。详细看代码注释。
   [输入]
      1 1
      *
      3 5
      *@*@*
      **@**
      *@*@*
      1 8
      @@****@*
      5 5 
      ****@
      *@@*@
      *@**@
      @@@*@
      @@**@
      0 0
   [输出] 
      0
      1
      2
      2
*/