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.shnenglu.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?