zoj 1709 Oil Deposits ——DFS入门题

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=709 题目大意： 　　给一个矩阵，*代表空地，@代表油田，并且@如果水平，竖直，对角线相邻的话就认为是一块油田，问有多少块油田。 　　思路就是DFS，从第一个字符开始搜，找到一个@就标记一下，cnt++，然后看它的八个方向上是不是有@，如果有，全部标记为*，不需要恢复现场。然后输出cnt的值就行了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;

char s[110][110];
bool flag;
int cnt, n, m;
int dir[8][2] = {{0,1},{0,-1},{-1,0},{1,0},{1,1},{-1,1},{1,-1},{-1,-1}};
void dfs(int i, int j){
  if (i < 0 || j < 0 || i > m || j > n) return;
  if (s[i][j] == '*') return;
  if (s[i][j] == '@') flag = true;
  s[i][j] = '*';
  for (int k = 0; k < 8; ++k){
    if (s[i+dir[k][0]][j+dir[k][1]] == '@'){
      dfs(i+dir[k][0], j+dir[k][1]);
    }
  }
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("zoj1709.in", "r", stdin);
#endif
  while (~scanf("%d%d", &m, &n) && (m+n)){
    cnt = 0; flag = false;
    for (int i = 0; i < m; ++i){
      scanf("%s", s[i]);
    }
    for (int i = 0; i < m; ++i){
      for (int j = 0; j < n; ++j){
        flag = false;
        dfs(i, j);
        if (flag) cnt++;
      }
    }
    printf("%d\n", cnt);
  }

  return 0;
}

自己写的，好久不1A了……虽然题目很简单，但还是很高兴~O(∩_∩)O哈哈~