HDU1198

这道题DFS,BFS,并查集好像都可以
觉得深搜跟并查集可能会更简单一些
 1 #include "iostream"
 2 #include "algorithm"
 3 #include "memory.h"
 4 #include "cmath"
 5 #include "string"
 6 using namespace std;
 7 #define MAXN 550
 8 
 9 
10 char s[15][6] = {
11     { "1100" }, {"0110"}, {"1001"}, {"0011"}, {"0101"}, {"1010"}, {"1110"}, {"1101"}, {"1011"}, {"0111"}, {"1111"}
12 };
13 int n, m,num;
14 int fa[MAXN*MAXN];
15 string a[550];
16 
17 int find(int x)
18 {
19     if (fa[x] < 0) return x;
20     return fa[x] = find(fa[x]);
21 }
22 
23 void merge(int a, int b)
24 {
25     int x = find(a);
26     int y = find(b);
27     if (x < y) {
28         fa[x] += fa[y];
29         fa[y] = x;
30     }
31     if (x > y) {
32         fa[y] += fa[x];
33         fa[x] = y;
34     }
35 }
36 
37 void judge(int i, int j, int x, int y)
38 {
39     if (y < m && s[a[i][j] - 'A'][2] == '1' && s[a[i][y] - 'A'][0] == '1') 
40         merge(i*m + j, i*m + y);
41     if (x < n && s[a[i][j] - 'A'][3] == '1' && s[a[x][j] - 'A'][1] == '1')
42         merge(i*m + j, x*m + j);
43 }
44 
45 
46 void init()
47 {
48     memset(fa,-1,sizeof(fa));
49     num = 0;
50 }
51 
52 int main()
53 {
54     while (cin >> n >> m) {
55         if (n < 1 || m < 1) break;
56         init();
57         for (int i = 0; i < n; ++i){
58             a[i].clear();
59             cin >> a[i];
60         }
61         for (int i = 0; i < n; ++ i)
62             for (int j = 0; j < m; ++j) {
63                 int x = i + 1;
64                 int y = j + 1; 
65                 judge(i,j,x,y);
66             }
67         for (int i = 0; i < n*m; ++i)
68             if (fa[i] < 0) num++;
69             //cout << fa[i] << " ";
70         cout << num << endl;
71     }
72     return 0;
73 }