题意：就是用一个球a去撞另外一个球b（如果两个相邻是撞不了的），球a停在球b前，球b被撞出去了，少了一个球咯，如果一行有多个球，那么就一个传一个咯，题目要求的结果是最后只剩下一个球。每次都得从头开始搜，我认为是不能只用结构体存储'O'的位置的，必须得用数组存储，因为，每次撞球后位置改变了，结构体存储的点的顺序是会变化的，而下一次搜索又是必须得按顺序开始搜的（即从左上角开始），如果对变化后的结构体排序的话，那么回溯回来又怎么办？反正我是想不到办法了，然后改成数组存储了。我写的挺复杂的，其实思路挺简单的。
View Code
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 int ins;
6 int flag;
7 char map[7][8];
8 char rem[12][8];//为了记忆，方便回溯来着
9
10 struct point
11 {
12 int x,y;
13 char dir ;
14 }p[15];//存储搜到的点和它的方向
15
16 int is_fur_up(int i,int j)//找一个点向上是否有'O'点，并返回该点的横坐标
17 {
18 int t;
19 for(t=i-1;t>=0;t--)
20 {
21 if(map[t][j]=='O')
22 return t;
23 }
24
25 return -1;
26 }
27
28 int is_fur_left(int i,int j)//同上理，方向是向左
29 {
30 int t;
31 for(t=j-1;t>=0;t--)
32 {
33 if(map[i][t]=='O')
34 return t;
35 }
36
37 return -1;
38 }
39
40 int is_fur_right(int i,int j)
41 {
42 int t;
43 for(t=j+1;t<8;t++)
44 {
45 if(map[i][t]=='O')
46 return t;
47 }
48
49 return -1;
50 }
51
52 int is_fur_down(int i,int j)
53 {
54 int t;
55 for(t=i+1;t<7;t++)
56 {
57 if(map[t][j]=='O')
58 return t;
59 }
60
61 return -1;
62 }
63
64 void dfs( int total )
65 {
66 //cout << total << " " << ins << endl;
67 if(total==ins-1)
68 {
69 for(int i=0;i<total;i++)
70 {
71 cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].dir<<endl;
72 }
73 flag=1;
74 return;
75 }
76 int i,j;
77 for(i=0;i<7;i++)
78 {
79 for(j=0;j<8;j++)
80 {
81 if(map[i][j]=='O')
82 {
83 int des=is_fur_up(i,j);//获得该方向上的'O'点的位置
84 int tem , mem ;
85 if(des!=-1&&i-des>1)//必须用》1这个，相邻的不能动
86 {
87 p[ total ].x=i;
88 p[ total ].y=j;
89 p[ total ].dir='U';
90 for(int c=0 ; c<7 ;c++ )//这个循环是用来记录在改变位置之前的值的，应该可以用memcpy（）整体复制
91 {
92 rem[total][c]=map[c][j];
93 }
94 map[i][j]='X';
95 map[des+1][j]='O';
96 tem = des;
97 while((mem=is_fur_up(tem,j))!=-1)//因为该方向上可能还有其他的值，得一个一个处理掉，但是这里就不用考虑相邻的问题了，能量一个传一个嘛
98 {
99 map[tem][j]='X';
100 map[mem+1][j]='O';
101 tem=mem;
102 }
103 map[tem][j]='X';
104 dfs( total+1 );
105 if( flag )
106 return ;
107 for(c=0; c<7 ;c++)//回溯，也可以用memcpy（）将值复制过来咯
108 map[c][j]=rem[total][c];
109 }
110
111 des=is_fur_left(i,j);
112 //cout << des <<endl;
113 if(des!=-1&&j-des>1)
114 {
115 p[ total ].x=i;
116 p[ total ].y=j;
117 p[ total ].dir='L';
118 for(int c=0; c<8 ;c++ )
119 rem[total][c]=map[i][c];
120 map[i][j]='X';
121 map[i][des+1] = 'O';
122 tem = des;
123 while( (mem = is_fur_left( i,tem ) )!=-1 )
124 {
125 map[i][tem] = 'X';
126 map[i][mem + 1] = 'O';
127 tem = mem;
128 }
129 map[i][tem] = 'X';
130 dfs(total+1);
131 if ( flag )
132 return ;
133 for(c=0 ; c<8 ;c++)
134 map[i][c] = rem[total][c];
135 }
136 des=is_fur_right(i,j);
137 //cout << des <<endl;
138 if( des != -1&&des - j > 1)
139 {
140 p[ total ].x=i;
141 p[ total ].y=j;
142 p[ total ].dir='R';
143 for(int c=0; c<8 ;c++ )
144 {
145 rem[total][c]=map[i][c];
146 //cout << rem[total][c];
147 }
148 //cout << endl;
149 map[i][j] = 'X';
150 map[i][des-1] ='O';
151 tem = des;
152 while( (mem = is_fur_right( i,tem ) )!=-1 )
153 {
154 map[i][tem]='X';
155 map[i][mem-1] = 'O';
156 tem = mem;
157 }
158 map[i][tem] = 'X';
159 dfs(total+1);
160 if( flag )
161 return ;
162 for(c=0 ; c<8 ;c++)
163 map[i][c] = rem[total][c];
164 }
165
166 des = is_fur_down ( i, j);
167 //cout << des <<endl;
168 if( des != -1 && des - i > 1)
169 {
170 p[ total ].x=i;
171 p[ total ].y=j;
172 p[ total ].dir='D';
173 for(int c=0 ; c<7 ;c++ )
174 {
175 rem[total][c]=map[c][j];
176 }
177 map[i][j] = 'X';
178 map[des-1][j] = 'O';
179 tem = des;
180 while( (mem = is_fur_down( tem ,j ) ) !=-1)
181 {
182 map[tem][j] = 'X';
183 map[mem-1][j] = 'O';
184 tem = mem;
185 }
186 map[tem][j] = 'X';
187 dfs( total+1 );
188 if ( flag )
189 return ;
190 for(c=0; c<7 ;c++)
191 map[c][j]=rem[total][c];
192 }
193 }
194 }
195 }
196 }
197
198 int main()
199 {
200 string a;
201 int count=0;
202 while(cin>>a)
203 {
204 int i,j;
205 ins=0;
206
207 for(i=0;i<7;i++)
208 {
209 if(i)
210 cin>>a;
211 for(j=0;j<8;j++)
212 {
213 map[i][j]=a[j];
214 if( a[j] == 'O')
215 ins++ ;
216 }
217 }
218 //cout<<ins << endl ;
219 if(count)//坑爹！
220 cout<< endl ;
221 flag=0;
222 cout<<"CASE #"<<++count<<":"<<endl;
223 dfs( 0 );
224
225 }
226
227 return 0;
228 }