UVa 572 Oil Deposits

　　给一个m*n的矩阵，数字是0或是1，统计其中八连块的个数，和《算法竞赛入门经典》6.4.1黑白图像一样，应该是那个的原型吧。

　　代码如下：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int maxn = 105;
 5 int mat[maxn][maxn], vis[maxn][maxn];
 6 
 7 void dfs(int x, int y)
 8 {
 9     if(vis[x][y] || !mat[x][y])   return;
10     vis[x][y] = 1;
11     dfs(x-1, y-1);   dfs(x-1, y);   dfs(x-1, y+1);
12     dfs(x, y-1);                    dfs(x, y+1);
13     dfs(x+1, y-1);   dfs(x+1, y);   dfs(x+1, y+1);
14 }
15 
16 int main()
17 {
18 #ifdef LOCAL
19     freopen("in", "r", stdin);
20 #endif
21     int m, n;
22     while(scanf("%d%d", &m , &n) != EOF && m)
23     {
24         char s[maxn];
25         memset(mat, 0, sizeof(mat));
26         memset(vis, 0, sizeof(vis));
27         for(int i = 0; i < m; i++)
28         {
29             scanf("%s", s);
30             for(int j = 0; j < n; j++)
31             {
32                 if(s[j] == '*')   mat[i+1][j+1] = 0;
33                 else if(s[j] == '@')   mat[i+1][j+1] = 1;
34             }
35         }
36         int cnt = 0;
37         for(int i = 1; i <= m; i++)
38             for(int j = 1; j <= n; j++)
39                 if(!vis[i][j] && mat[i][j])
40                 {
41                     cnt++;
42                     dfs(i, j);
43                 }
44         printf("%d\n", cnt);
45     }
46     return 0;
47 }

　　上面是用递归的方式实现的，也可用显式栈来代替递归，代码如下：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <stack>
 4 using namespace std;
 5 
 6 const int maxn = 105;
 7 int mat[maxn][maxn], vis[maxn][maxn];
 8 int m, n;
 9 
10 const int dir[][2] = { {1, 1}, {1, 0}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1,-1} };
11 
12 struct Pos
13 {
14     int x, y;
15 };
16 
17 void dfs(int x, int y)
18 {
19     stack<Pos> s;
20     Pos t;
21     t.x = x;
22     t.y = y;
23     s.push(t);
24     while(!s.empty())
25     {
26         t = s.top();
27         s.pop();
28         int x = t.x, y = t.y;
29         for(int i = 0; i < 8; i++)
30         {
31             int nx, ny;
32             nx = x + dir[i][0];
33             ny = y + dir[i][1];
34             if(nx >= 0 && nx < m && ny >= 0 && ny < n)
35                 if(mat[nx][ny] && !vis[nx][ny])
36                 {
37                     t.x = nx;
38                     t.y = ny;
39                     s.push(t);
40                     vis[nx][ny] = 1;
41                 }
42         }
43     }
44 }
45 
46 
47 int main()
48 {
49 #ifdef LOCAL
50     freopen("in", "r", stdin);
51 #endif
52     while(scanf("%d%d", &m, &n) != EOF && m)
53     {
54         char s[maxn];
55         memset(mat, 0, sizeof(mat));
56         memset(vis, 0, sizeof(vis));
57         for(int i = 0; i < m; i++)
58         {
59             scanf("%s", s);
60             for(int j = 0; j < n; j++)
61                 if(s[j] == '@')   mat[i][j] = 1;
62         }
63         int cnt = 0;
64         for(int i = 0; i < m; i++)
65             for(int j = 0; j < n; j++)
66                 if(!vis[i][j] && mat[i][j])
67                 {
68                     cnt++;
69                     dfs(i, j);
70                 }
71         printf("%d\n", cnt);
72     }
73     return 0;
74 }