2010年03月04日星期四.pku1448 && nwerc 2001 cube 超麻烦的搜索
pku1448:这题就两个字弓虽
给出六个平面，问是不是能拼成一个立方体。
每个面有8种状态， 0,90,180,270,然后还有镜面翻转之后同样的四个状态。
然后可以选一个当底面，另外5个全排列。
复杂度是 5! * 8 ^ 5...如果剪枝不够好的话就会TLE了。。
我用的方法是把立方体按照这种方法展开：
/*
* oh my god!!
. [0][0] [0][1] [0][2] [0][3] [0][4] [0][5]
. 2[1][0] [1][1] [1][2] [1][3] [1][4] [1][5]
. [2][0] [2][1] [2][2] [2][3] [2][4] [2][5]
. [3][0] [3][1] [3][2] [3][3] [3][4] [3][5]
. [4][0] [4][1] [4][2] [4][3] [4][4] [4][5]
. [5][0] [5][1] [5][2] [5][3] [5][4] [5][5]
.
. [0][0] [0][1] [0][2] [0][3] [0][4] [0][5] [0][0] [0][1] [0][2] [0][3] [0][4] [0][5] [0][0] [0][1] [0][2] [0][3] [0][4] [0][5] [0][0] [0][1] [0][2] [0][3] [0][4] [0][5]
. [1][0] [1][1] [1][2] [1][3] [1][4] [1][5] [1][0] [1][1] [1][2] [1][3] [1][4] [1][5] [1][0] [1][1] [1][2] [1][3] [1][4] [1][5] [1][0] [1][1] [1][2] [1][3] [1][4] [1][5]
. [2][0] [2][1] [2][2] [2][3] [2][4] [2][5] [2][0] [2][1] [2][2] [2][3] [2][4] [2][5] [2][0] [2][1] [2][2] [2][3] [2][4] [2][5] [2][0] [2][1] [2][2] [2][3] [2][4] [2][5]
. [3][0] [3][1] [3][2] [3][3] [3][4] [3][5] [3][0] [3][1] [3][2] [3][3] [3][4] [3][5] 4[3][0] [3][1] [3][2] [3][3] [3][4] [3][5] 5[3][0] [3][1] [3][2] [3][3] [3][4] [3][5]
.1[4][0] [4][1] [4][2] [4][3] [4][4] [4][5] 0[4][0] [4][1] [4][2] [4][3] [4][4] [4][5] [4][0] [4][1] [4][2] [4][3] [4][4] [4][5] [4][0] [4][1] [4][2] [4][3] [4][4] [4][5]
. [5][0] [5][1] [5][2] [5][3] [5][4] [5][5] [5][0] [5][1] [5][2] [5][3] [5][4] [5][5] [5][0] [5][1] [5][2] [5][3] [5][4] [5][5] [5][0] [5][1] [5][2] [5][3] [5][4] [5][5]
.
. [0][0] [0][1] [0][2] [0][3] [0][4] [0][5]
. [1][0] [1][1] [1][2] [1][3] [1][4] [1][5]
. [2][0] [2][1] [2][2] [2][3] [2][4] [2][5]
. 3[3][0] [3][1] [3][2] [3][3] [3][4] [3][5]
. [4][0] [4][1] [4][2] [4][3] [4][4] [4][5]
. [5][0] [5][1] [5][2] [5][3] [5][4] [5][5]
* */然后找出角点和边的对应关系,之后检查每个点是否之后一个X。
1 bool ckvertex()
2 {
3 int a;
4 a = p[c[0]][0][0] + p[c[1]][0][5] + p[c[2]][5][0]; if (a != 1) { return false; }
5 a = p[c[0]][0][5] + p[c[2]][5][5] + p[c[4]][0][0]; if (a != 1) { return false; }
6 a = p[c[0]][5][0] + p[c[1]][5][5] + p[c[3]][0][0]; if (a != 1) { return false; }
7 a = p[c[0]][5][5] + p[c[4]][5][0] + p[c[3]][0][5]; if (a != 1) { return false; }
8 //
9 a = p[c[1]][0][0] + p[c[2]][0][0] + p[c[5]][0][5]; if (a != 1) { return false; }
10 a = p[c[1]][5][0] + p[c[3]][5][0] + p[c[5]][5][5]; if (a != 1) { return false; }
11 a = p[c[2]][0][5] + p[c[4]][0][5] + p[c[5]][0][0]; if (a != 1) { return false; }
12 a = p[c[3]][5][5] + p[c[4]][5][5] + p[c[5]][5][0]; if (a != 1) { return false; }
13 return true;
14 }
15 http://www.cppblog.com/schindlerlee/
16 bool ckedge()
17 {
18 int i,a;
19 for (i = 1;i <= 4;i++) {
20 a = p[c[0]][0][i] + p[c[2]][5][i];if(a != 1) return false;
21 a = p[c[0]][5][i] + p[c[3]][0][i];if(a != 1) return false;
22 a = p[c[0]][i][0] + p[c[1]][i][5];if(a != 1) return false;
23 a = p[c[0]][i][5] + p[c[4]][i][0];if(a != 1) return false;
24 //bottom
25 a = p[c[1]][0][i] + p[c[2]][i][0];if(a != 1) return false;
26 a = p[c[1]][5][i] + p[c[3]][5-i][0];if(a != 1) return false;
27 a = p[c[4]][0][i] + p[c[2]][5-i][5];if(a != 1) return false;
28 a = p[c[3]][i][5] + p[c[4]][5][i];if(a != 1) return false;
29 //vertical
30 a = p[c[2]][0][i] + p[c[5]][0][5-i];if(a != 1) return false;
31 a = p[c[3]][5][i] + p[c[5]][5][5-i];if(a != 1) return false;
32 a = p[c[4]][i][5] + p[c[5]][i][0];if(a != 1) return false;
33 a = p[c[1]][i][0] + p[c[5]][i][5];if(a != 1) return false;
34 //up
35 }
36 return true;
37 }
不能把这两个函数放在递归出口，一定会超时。。。
需要把这两个函数做成剪枝才能不超时。
1
2 char p[6][6][6];
3 int c[6] = {0,1,2,3,4,5};
4
5 void rotate90(char p[6][6])
6 {
7 char t;
8 char tmp[6];
9 t = p[0][0]; // vertex
10 p[0][0] = p[0][5];
11 p[0][5] = p[5][5];
12 p[5][5] = p[5][0];
13 p[5][0] = t;
14
15 for (int i = 1;i <= 4;i++) { tmp[i] = p[0][i]; }
16 for (int i = 1;i <= 4;i++) { p[0][i] = p[i][5]; }
17 for (int i = 1;i <= 4;i++) { p[i][5] = p[5][5-i]; }
18 for (int i = 1;i <= 4;i++) { p[5][i] = p[i][0]; }
19 for (int i = 1;i <= 4;i++) { p[i][0] = tmp[5-i]; }
20 }
21
22 void reflect(char p[6][6])
23 {
24 int i;
25 char tmp[6];
26 for (i = 0;i < 6;i++) { tmp[i] = p[0][i]; }
27 for (i = 0;i < 6;i++) { p[0][i] = p[5][i]; }
28 for (i = 0;i < 6;i++) { p[5][i] = tmp[i]; }
29 swap(p[1][0],p[4][0]);
30 swap(p[2][0],p[3][0]);
31
32 swap(p[1][5],p[4][5]);
33 swap(p[2][5],p[3][5]);
34 }
35
36 bool dfs(int depth)
37 {
38 int a,i;
39 if (depth == 2) {
40 for (i = 1;i <= 4;i++) {
41 a = p[c[0]][i][0] + p[c[1]][i][5];if(a != 1) return false;
42 }
43 }
44
45 if (depth == 3) {
46 for (i = 1;i <= 4;i++) {
47 a = p[c[1]][0][i] + p[c[2]][i][0];if(a != 1) return false;
48 a = p[c[0]][0][i] + p[c[2]][5][i];if(a != 1) return false;
49 }
50 a = p[c[0]][0][0] + p[c[1]][0][5] + p[c[2]][5][0]; if (a != 1) { return false; }
51 }
52
53 if (depth == 4) {
54 for (i = 1;i <= 4;i++) {
55 a = p[c[1]][5][i] + p[c[3]][5-i][0];if(a != 1) return false;
56 a = p[c[0]][5][i] + p[c[3]][0][i];if(a != 1) return false;
57 }
58 a = p[c[0]][5][0] + p[c[1]][5][5] + p[c[3]][0][0]; if (a != 1) { return false; }
59 }
60
61 if (depth == 5) {
62 for (i = 1;i <= 4;i++) {
63 a = p[c[3]][i][5] + p[c[4]][5][i];if(a != 1) return false;
64 a = p[c[0]][i][5] + p[c[4]][i][0];if(a != 1) return false;
65 a = p[c[4]][0][i] + p[c[2]][5-i][5];if(a != 1) return false;
66 }
67 a = p[c[0]][0][5] + p[c[2]][5][5] + p[c[4]][0][0]; if (a != 1) { return false; }
68 a = p[c[0]][5][5] + p[c[4]][5][0] + p[c[3]][0][5]; if (a != 1) { return false; }
69 }
70
71 if (depth == 6) {
72 for (i = 1;i <= 4;i++) {
73 a = p[c[3]][5][i] + p[c[5]][5][5-i];if(a != 1) return false;
74 a = p[c[4]][i][5] + p[c[5]][i][0];if(a != 1) return false;
75 a = p[c[1]][i][0] + p[c[5]][i][5];if(a != 1) return false;
76 a = p[c[2]][0][i] + p[c[5]][0][5-i];if(a != 1) return false;
77 }
78 //
79 a = p[c[1]][0][0] + p[c[2]][0][0] + p[c[5]][0][5]; if (a != 1) { return false; }
80 a = p[c[1]][5][0] + p[c[3]][5][0] + p[c[5]][5][5]; if (a != 1) { return false; }
81 a = p[c[2]][0][5] + p[c[4]][0][5] + p[c[5]][0][0]; if (a != 1) { return false; }
82 a = p[c[3]][5][5] + p[c[4]][5][5] + p[c[5]][5][0]; if (a != 1) { return false; }
83
84 return true;
85 }
86
87 for (int i = 0;i < 4;i++) {
88 rotate90(p[c[depth]]);
89 if(dfs(depth + 1))
90 return true;
91 }
92 reflect(p[c[depth]]);
93 for (int i = 0;i < 4;i++) {
94 rotate90(p[c[depth]]);
95 if(dfs(depth + 1))
96 return true;
97 }
98 reflect(p[c[depth]]);
99 return false;
100 }
101
102 bool judge()
103 {
104 int i,j,k;
105 do {
106 if(dfs(1))
107 return true;
108 }while(next_permutation(c + 1,c + 6));
109 }
110
111 int main()
112 {
113 int i,j,k,testcase,testid = 1;
114 scanf("%d\n",&testcase);
115 while (testcase--) {
116 for (i = 0;i < 6;i++) { c[i] = i; }
117 for (j = 0;j < 6;j++) {
118 for (i = 0;i < 6;i++) {
119 for (k = 0;k < 6;k++) {
120 p[i][j][k] = getchar();
121 }
122 getchar();
123 }
124 getchar();
125 }
126 for (i = 0;i < 6;i++) {
127 for (j = 0;j < 6;j++) {
128 for (k = 0;k < 6;k++) {
129 p[i][j][k] = (p[i][j][k] == 'X');
130 }
131 }
132 }
133 printf("Scenario #%d:\n",testid++);
134 if (judge()) {
135 printf("Yes\n");
136 }else {
137 printf("No\n");
138 }
139 putchar(10), getchar();
140 }
141 return 0;
142 }
143
144