uva 352 - The Seasonal War

/*

Problem link

Type: Graph, flood fill

*/

 1  #include <iostream>
 2  #include <cstdio>
 3  #include <cstring>
 4  #include <cmath>
 5  #include <cstdlib>
 6  using namespace std;
 7  
 8  const int dx[8] = {0,-1,-1,-1,0,1,1,1};
 9  const int dy[8] = {-1,-1,0,1,1,1,0,-1};
10  const int maxn = 30;
11  
12  bool isin(int, int);
13  void fill(int, int);
14  
15  int a[30][30];
16  bool fre[30][30];
17  int n;
18  
19  int main()
20  {
21      int test = 0;
22      while (!cin.eof())
23      {
24          cin >> n;
25          if (cin.eof()) break;
26          test++;
27          char ch;
28          for (int i=1; i<=n; i++)
29              for (int j=1; j<=n; j++)
30              {
31                  cin >> ch;
32                  a[i][j] = int(ch)-48;
33              }
34          memset(fre,true,sizeof(fre));
35          int result = 0;
36          for (int i=1; i<=n; i++)
37              for (int j=1; j<=n; j++)
38                  if (a[i][j]==1 && fre[i][j])
39                  {
40                      result++;
41                      fill(i,j);
42                  }
43          printf("Image number %d contains %d war eagles.\n",test,result);
44      }
45      return 0;
46  }
47  
48  bool isin(int x, int y) {
49      return(x>=1 && y>=1 && x<=n && y<=n);
50  }
51  
52  void fill(int x, int y) {
53      fre[x][y] = false;
54      for (int k=0; k<8; k++)
55      {
56          int xx = x+dx[k];
57          int yy = y+dy[k];
58          if (isin(xx,yy)&& fre[xx][yy] && a[xx][yy]==1) fill(xx,yy);
59      }
60  }
61  
62