UVa 1572 (拓扑排序) Self-Assembly

浏览数：75 / 时间：2015年06月08日

题意：

有n种正放形，每种正方形的数量可视为无限多。已知边与边之间的结合规则，而且正方形可以任意旋转和反转，问这n中正方形是否可以拼成无限大的图案。

分析：

首先因为可以旋转和反转，所以可以保证在拼接的过程中正方形不会自交。

把边的标号看成点，将正方形的边界A+变成B+可以看做是一条边。比如说，一个正方形中有A-和B+两条边，则A-与其他正方形中A+结合后，结合前边界为A-，结合后变为B+。

这样就得到图中的一条有向边A+ → B+

如果能在图中找到一个环，则可以无限循环拼接正方形。

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 int G[52][52], c[52];
 5 int n;
 6 
 7 int ID(char a, char b) { return (a - ‘A‘) * 2 + (b == ‘+‘ ? 1 : 0); }
 8 
 9 void connect(char a1, char a2, char b1, char b2)
10 {
11     if(a1 == ‘0‘ || b1 == ‘0‘) return;
12     int u = ID(a1, a2) ^ 1;
13     int v = ID(b1, b2);
14     G[u][v] = 1;
15 }
16 
17 bool dfs(int u)
18 {//是否存在包含u的环
19     c[u] = -1;  //正在访问
20     for(int v = 0; v < 52; ++v) if(G[u][v])
21     {
22         if(c[v] < 0) return true;
23         else if(!c[v] && dfs(v)) return true;
24     }
25     c[u] = 1;   //访问结束
26     return false;
27 }
28 
29 bool find_circle()
30 {
31     memset(c, 0, sizeof(c));
32     for(int u = 0; u < 52; ++u) if(!c[u])
33         if(dfs(u)) return true;
34     return false;
35 }
36 
37 int main()
38 {
39     //freopen("in.txt", "r", stdin);
40     while(scanf("%d", &n) == 1 && n)
41     {
42         memset(G, 0, sizeof(G));
43         while(n--)
44         {
45             char s[10];
46             scanf("%s", s);
47             for(int i = 0; i < 4; ++i)
48                 for(int j = 0; j < 4; ++j) if(i != j)
49                     connect(s[i*2], s[i*2+1], s[j*2], s[j*2+1]);
50         }
51 
52         if(find_circle()) puts("unbounded");
53         else puts("bounded");
54     }
55 
56     return 0;
57 }