題目：
不用多解釋了吧，給出每個(gè)小塊，可以旋轉(zhuǎn)，求一種拼圖方案
題解：
就是基本的回溯法
搜索的時(shí)候注意下次序，可以剪枝不少~
這種搜索題我喜歡用面向?qū)ο蟮姆椒▉?lái)寫(xiě)，很清楚，不同意錯(cuò)，代碼也很容易看懂。大家看代碼吧
代碼：
1
/**//*
2
Source Code
3
4Problem: 1224 User: yzhw
5Memory: 684K Time: 32MS
6Language: G++ Result: Accepted
7Source Code
8
*/
9
# include <iostream>
10# include <string>
11# include <cstring>
12# include <cstdio>
13using namespace std;
14struct piece
15
{
16 char type[4][5],id[5];
17 int start;
18 void TurnRight()
19
{
20 start=(start+1)%4;
21
}
22 char *get(int pos)
23 {
24 return type[(start+pos)%4];
25 }
26 void print(char *first,char *second,char *third)
27 {
28 strcat(first," ");
29 strcat(first,get(0));
30 strcat(first," ");
31 strcat(second,get(3));
32 strcat(second," ");
33 strcat(second,id);
34 strcat(second," ");
35 strcat(second,get(1));
36 strcat(second," ");
37 strcat(third," ");
38 strcat(third,get(2));
39 strcat(third," ");
40 }
41}data[9];
42piece ans[9];
43bool used[9];
44inline bool match(char *a,char *b)
45{
46 return a[0]==b[0]&&(a[1]=='L'&&b[1]=='R'||a[1]=='R'&&b[1]=='L');
47}
48bool search(int pos)
49{
50 if(pos==9) return true;
51 else
52 {
53 switch(pos)
54 {
55 case 0:
56 for(int i=0;i<9;i++)
57 if(!used[i])
58 {
59 ans[pos]=data[i];
60 used[i]=true;
61 if(search(pos+1)) return true;
62 used[i]=false;
63 }
64 break;
65 case 1:
66 for(int i=0;i<9;i++)
67 if(!used[i])
68 {
69 ans[pos]=data[i];
70 used[i]=true;
71 for(int j=0;j<4;j++)
72 {
73 if(match(ans[pos].get(2),ans[0].get(0))&&search(pos+1)) return true;
74 ans[pos].TurnRight();
75 }
76 used[i]=false;
77 }
78 break;
79 case 2:
80 for(int i=0;i<9;i++)
81 if(!used[i])
82 {
83 ans[pos]=data[i];
84 used[i]=true;
85 for(int j=0;j<4;j++)
86 {
87 if(match(ans[pos].get(3),ans[0].get(1))&&search(pos+1)) return true;
88 ans[pos].TurnRight();
89 }
90 used[i]=false;
91 }
92 break;
93 case 3:
94 for(int i=0;i<9;i++)
95 if(!used[i])
96 {
97 ans[pos]=data[i];
98 used[i]=true;
99 for(int j=0;j<4;j++)
100 {
101 if(match(ans[pos].get(0),ans[0].get(2))&&search(pos+1)) return true;
102 ans[pos].TurnRight();
103 }
104 used[i]=false;
105 }
106 break;
107 case 4:
108 for(int i=0;i<9;i++)
109 if(!used[i])
110 {
111 ans[pos]=data[i];
112 used[i]=true;
113 for(int j=0;j<4;j++)
114 {
115 if(match(ans[pos].get(1),ans[0].get(3))&&search(pos+1)) return true;
116 ans[pos].TurnRight();
117 }
118 used[i]=false;
119 }
120 break;
121 case 5:
122 for(int i=0;i<9;i++)
123 if(!used[i])
124 {
125 ans[pos]=data[i];
126 used[i]=true;
127 for(int j=0;j<4;j++)
128 {
129 if(match(ans[pos].get(1),ans[1].get(3))&&match(ans[pos].get(2),ans[4].get(0))&&search(pos+1)) return true;
130 ans[pos].TurnRight();
131 }
132 used[i]=false;
133 }
134 break;
135 case 6:
136 for(int i=0;i<9;i++)
137 if(!used[i])
138 {
139 ans[pos]=data[i];
140 used[i]=true;
141 for(int j=0;j<4;j++)
142 {
143 if(match(ans[pos].get(3),ans[1].get(1))&&match(ans[pos].get(2),ans[2].get(0))&&search(pos+1)) return true;
144 ans[pos].TurnRight();
145 }
146 used[i]=false;
147 }
148 break;
149 case 7:
150 for(int i=0;i<9;i++)
151 if(!used[i])
152 {
153 ans[pos]=data[i];
154 used[i]=true;
155 for(int j=0;j<4;j++)
156 {
157 if(match(ans[pos].get(0),ans[2].get(2))&&match(ans[pos].get(3),ans[3].get(1))&&search(pos+1)) return true;
158 ans[pos].TurnRight();
159 }
160 used[i]=false;
161 }
162 break;
163 case 8:
164 for(int i=0;i<9;i++)
165 if(!used[i])
166 {
167 ans[pos]=data[i];
168 used[i]=true;
169 for(int j=0;j<4;j++)
170 {
171 if(match(ans[pos].get(0),ans[4].get(2))&&match(ans[pos].get(1),ans[3].get(3))&&search(pos+1)) return true;
172 ans[pos].TurnRight();
173 }
174 used[i]=false;
175 }
176 break;
177 };
178 return false;
179 }
180}
181int main()
182{
183 int id;
184 while(true)
185 {
186 scanf("%d",&id);
187 if(!id) break;
188 for(int i=0;i<9;i++)
189 {
190 scanf("%s",data[i].id);
191 data[i].start=0;
192 for(int j=0;j<4;j++)
193 scanf("%s",data[i].type[j]);
194 }
195 printf("%d:\n",id);
196 memset(used,false,sizeof(used));
197 switch(search(0))
198 {
199 case true:
200 {
201 char first[100],second[100],third[100];
202 first[0]=second[0]=third[0]='\0';
203 ans[5].print(first,second,third);
204 ans[1].print(first,second,third);
205 ans[6].print(first,second,third);
206 printf("%s\n%s\n%s\n\n",first,second,third);
207 first[0]=second[0]=third[0]='\0';
208 ans[4].print(first,second,third);
209 ans[0].print(first,second,third);
210 ans[2].print(first,second,third);
211 printf("%s\n%s\n%s\n\n",first,second,third);
212 first[0]=second[0]=third[0]='\0';
213 ans[8].print(first,second,third);
214 ans[3].print(first,second,third);
215 ans[7].print(first,second,third);
216 printf("%s\n%s\n%s\n\n",first,second,third);
217 }
218 break;
219 case false:
220 printf("No Solution\n\n");
221 break;
222 };
223 }
224 return 0;
225}