uva 572 - Oil Deposits

 1  /*
 2  Problem link
 3  Type: Graph
 4  Algorithm: DFS
 5  */
 6  #include <iostream>
 7  #include <cstdio>
 8  #include <cstring>
 9  #include <cmath>
10  
11  using namespace std;
12  const int dx[8] = {0,-1,-1,-1,0,1,1,1};
13  const int dy[8] = {-1,-1,0,1,1,1,0,-1};
14  const int maxn = 110;
15  
16  char a[maxn][maxn];
17  int d[maxn][maxn];
18  int n,m;
19  
20  bool ReadFile();
21  bool IsIn(int x, int y);
22  void DFS(int x, int y, int cnt);
23  
24  int main()
25  {
26      while (ReadFile())
27      {
28          int result = 0;
29          for (int i=1; i<=n; i++)
30              for (int j=1; j<=m; j++) d[i][j] = 0;
31          for (int i=1; i<=n; i++)
32              for (int j=1; j<=m; j++)
33                  if (d[i][j]==0 && a[i][j]=='@')
34                  {
35                      result++;
36                      DFS(i,j,result);
37                  }
38          cout << result << endl;
39      }
40      return 0;
41  }
42  
43  bool ReadFile()
44  {
45      cin >> n >> m;
46      if (n==0 && m==0) return false;
47      for (int i=1; i<=n; i++)
48          for (int j=1; j<=m; j++) cin >> a[i][j];
49      return true;
50  }
51  
52  void DFS(int x, int y, int cnt)
53  {
54      d[x][y] = cnt;
55      for (int k=0; k<8; k++)
56      {
57          int xx = x+dx[k];
58          int yy = y+dy[k];
59          if (IsIn(xx,yy) && a[xx][yy]=='@' && d[xx][yy]==0) DFS(xx,yy,cnt);
60      }
61  }
62  
63  bool IsIn(int x, int y)
64  {
65      return (x>=1 && y>=1 && x<=n && y<=m);
66  }