算法训练 Lift and Throw  
时间限制：3.0s   内存限制：256.0MB
    
问题描述
　　给定一条标有整点(1, 2, 3, ...)的射线. 定义两个点之间的距离为其下标之差的绝对值.
　　Laharl, Etna, Flonne一开始在这条射线上不同的三个点, 他们希望其中某个人能够到达下标最大的点.
　　每个角色只能进行下面的3种操作, 且每种操作不能每人不能进行超过一次.
　　1.移动一定的距离
　　2.把另一个角色高举过头
　　3.将举在头上的角色扔出一段距离
　　每个角色有一个movement range参数, 他们只能移动到没有人的位置, 并且起点和终点的距离不超过movement range.
　　如果角色A和另一个角***距离为1, 并且角***没有被别的角色举起, 那么A就能举起B. 同时, B会移动到A的位置,B原来所占的位置变为没有人的位置. 被举起的角色不能进行任何操作, 举起别人的角色不能移动.同时, 每个角色还有一个throwing range参数, 即他能把举起的角色扔出的最远的距离. 注意, 一个角色只能被扔到没有别的角色占据的位置. 我们认为一个角色举起另一个同样举起一个角色的角色是允许的. 这种情况下会出现3个人在同一个位置的情况. 根据前面的描述, 这种情况下上面的两个角色不能进行任何操作, 而最下面的角色可以同时扔出上面的两个角色. 你的任务是计算这些角色能够到达的位置的最大下标, 即最大的数字x, 使得存在一个角色能够到达x.
输入格式
　　输入共三行, 分别为Laharl, Etna, Floone的信息.
　　每一行有且仅有3个整数, 描述对应角色的初始位置, movement range, throwing range.
　　数据保证3个角色的初始位置两两不相同且所有的数字都在1到10之间.</div>
输出格式
　　仅有1个整数, 即Laharl, Etna, Flonne之一能到达的最大距离.
样例输入
9 3 3
4 3 1
2 3 3
样例输出
15
样例说明
　　一开始Laharl在位置9, Etna在位置4, Flonne在位置2.
　　首先, Laharl移动到6.
　　然后Flonne移动到位置5并且举起Etna.
　　Laharl举起Flonne将其扔到位置9.
　　Flonne把Etna扔到位置12.
　　Etna移动到位置15.
 
我想的思路是一人有三种操作，分别是移动，举起旁边的，扔自己上面的。三个人就是九种。
然后九种操作进行深度搜索。
样例给过了，但提交只有两组数据对了。
做了两晚上都没调好，我感觉我的思路应该没有错误。
 如果你有思路，希望告知我。
递归的程序虽然比较好想，但是稍微一复杂根本就没法调bug啊，很容易迷失在不知第几层。。。 
  1 #include <iostream>
  2 #include <cstdio>
  3 
  4 using namespace std;
  5 
  6 typedef struct node{
  7     int loca;
  8     int moverange;
  9     int throwrange;
 10 };
 11 struct node a[4];
 12 int w[100]={0};
 13 int is_move[4]={0};
 14 int is_lift[4]={0};
 15 int is_throw[4]={0};
 16 int is_belifted[4]={0};
 17 int ans=0;
 18 int step[10]={0};
 19 
 20 int dfs();
 21 //第一个人的第一种操作，移动
 22 void fun11(){
 23     if(!is_move[1]){
 24         int t=a[1].loca+a[1].moverange;
 25         for(int i=a[1].loca-a[1].moverange; i<=t; i++){
 26             if(!w[i] && i>=0){
 27                 int t1=w[a[1].loca];
 28                 int t2=a[1].loca;
 29                 int t3=is_move[1];
 30                 w[a[1].loca]=0;
 31                 w[i]=1;
 32                 a[1].loca=i;
 33                 is_move[1]=1;
 34                 dfs();
 35                 w[a[1].loca]=t1;
 36                 w[i]=0;
 37                 a[1].loca=t2;
 38                 is_move[1]=t3;
 39             }
 40 
 41         }
 42     }
 43 }
 44 //第一个人的第二种操作，举起两边的
 45 void fun12(){
 46     for(int i=1;i<=3;i++){
 47         if(w[a[1].loca-1]==i){
 48             int t1=w[a[1].loca-1];
 49             int t2=is_belifted[i];
 50             int t3=is_lift[1];
 51 
 52             w[a[1].loca-1]=0;
 53             is_belifted[i]=1;
 54             is_lift[1]=i;
 55             dfs();
 56 
 57             w[a[1].loca-1]=t1;
 58             is_belifted[i]=t2;
 59             is_lift[1]=t3;
 60         }
 61         if(w[a[1].loca+1]==i){
 62             int t1=w[a[1].loca+1];
 63             int t2=is_belifted[i];
 64             int t3=is_lift[1];
 65             w[a[1].loca+1]=0;
 66             is_belifted[i]=1;
 67             is_lift[1]=i;
 68             dfs();
 69             w[a[1].loca+1]=t1;
 70             is_belifted[i]=t2;
 71             is_lift[1]=t3;
 72         }
 73     }
 74 }
 75 //第一个人的第三种操作，扔自己上面的
 76 void fun13(){
 77     if(!is_throw[1] && is_lift[1]!=0){
 78         for(int i=a[1].loca-a[1].throwrange; i<=a[1].loca+a[1].throwrange; i++){
 79             if(!w[i] && i>=0){
 80                 int t1=w[a[1].loca];
 81                 int t2=w[i];
 82                 int t3=a[1].loca;
 83                 int t4=is_throw[1];
 84                 w[a[1].loca]=0;
 85                 w[i]=is_lift[1];
 86                 a[1].loca=i;
 87                 is_throw[1]=1;
 88                 dfs();
 89                 w[a[1].loca]=t1;
 90                 w[i]=t2;
 91                 a[1].loca=t3;
 92                 is_throw[1]=t4;
 93             }
 94 
 95         }
 96     }
 97 }
 98 
 99 //第二个人的第一种操作，移动
100 void fun21(){
101     if(!is_move[2]){
102         int t=a[2].loca+a[2].moverange;
103         for(int i=a[2].loca-a[2].moverange; i<=t; i++){
104             if(!w[i] && i>=0){
105                 int t1=w[a[2].loca];
106                 int t2=a[2].loca;
107                 int t3=is_move[2];
108                 w[a[2].loca]=0;
109                 w[i]=2;
110                 a[2].loca=i;
111                 is_move[2]=1;
112                 dfs();
113                 w[a[2].loca]=t1;
114                 w[i]=0;
115                 a[2].loca=t2;
116                 is_move[2]=t3;
117             }
118 
119         }
120     }
121 }
122 //第二个人的第二种操作，举起两边的
123 void fun22(){
124     for(int i=1;i<=3;i++){
125         if(w[a[2].loca-1]==i){
126             int t1=w[a[2].loca-1];
127             int t2=is_belifted[i];
128             int t3=is_lift[2];
129             w[a[2].loca-1]=0;
130             is_belifted[i]=2;
131             is_lift[2]=i;
132             dfs();
133             w[a[2].loca-1]=t1;
134             is_belifted[i]=t2;
135             is_lift[2]=t3;
136         }
137         if(w[a[2].loca+1]==i){
138             int t1=w[a[2].loca+1];
139             int t2=is_belifted[i];
140             int t3=is_lift[2];
141             w[a[2].loca+1]=0;
142             is_belifted[i]=2;
143             is_lift[2]=i;
144             dfs();
145             w[a[2].loca+1]=t1;
146             is_belifted[i]=t2;
147             is_lift[2]=t3;
148         }
149     }
150 }
151 //第二个人的第三种操作，扔自己上面的
152 void fun23(){
153     if(!is_throw[2] && is_lift[2]!=0){
154         for(int i=a[2].loca-a[2].throwrange; i<=a[2].loca+a[2].throwrange; i++){
155             if(!w[i] && i>=0){
156                 int t1=w[a[2].loca];
157                 int t2=w[i];
158                 int t3=a[2].loca;
159                 int t4=is_throw[2];
160                 w[a[2].loca]=0;
161                 w[i]=is_lift[2];
162                 a[2].loca=i;
163                 is_throw[2]=1;
164                 dfs();
165                 w[a[2].loca]=t1;
166                 w[i]=t2;
167                 a[2].loca=t3;
168                 is_throw[2]=t4;
169             }
170 
171         }
172     }
173 }
174 //第三个人的第一种操作，移动
175 void fun31(){
176     if(!is_move[3]){
177         int t=a[3].loca+a[3].moverange;
178         for(int i=a[3].loca-a[3].moverange; i<=t; i++){
179             if(!w[i] && i>=0){
180                 int t1=w[a[3].loca];
181                 int t2=a[3].loca;
182                 int t3=is_move[3];
183                 w[a[3].loca]=0;
184                 w[i]=3;
185                 a[3].loca=i;
186                 is_move[3]=1;
187                 dfs();
188                 w[a[3].loca]=t1;
189                 w[i]=0;
190                 a[3].loca=t2;
191                 is_move[3]=t3;
192             }
193 
194         }
195     }
196 }
197 //第三个人的第二种操作，举起两边的
198 void fun32(){
199     for(int i=1;i<=3;i++){
200         if(w[a[3].loca-1]==i){
201             int t1=w[a[3].loca-1];
202             int t2=is_belifted[i];
203             int t3=is_lift[3];
204             w[a[3].loca-1]=0;
205             is_belifted[i]=3;
206             is_lift[3]=i;
207             dfs();
208             w[a[3].loca-1]=t1;
209             is_belifted[i]=t2;
210             is_lift[3]=t3;
211         }
212         if(w[a[3].loca+1]==i){
213             int t1=w[a[3].loca-1];
214             int t2=is_belifted[i];
215             int t3=is_lift[3];
216             w[a[3].loca+1]=0;
217             is_belifted[i]=3;
218             is_lift[3]=i;
219             dfs();
220             w[a[3].loca+1]=t1;
221             is_belifted[i]=t2;
222             is_lift[3]=t3;
223         }
224     }
225 }
226 //第三个人的第三种操作，扔自己上面的
227 void fun33(){
228     if(!is_throw[3] && is_lift[3]!=0){
229         for(int i=a[3].loca-a[3].throwrange; i<=a[3].loca+a[3].throwrange; i++){
230             if(!w[i] && i>=0){
231                 int t1=w[a[3].loca];
232                 int t2=w[i];
233                 int t3=a[3].loca;
234                 int t4=is_throw[3];
235                 w[a[3].loca]=0;
236                 w[i]=is_lift[3];
237                 a[3].loca=i;
238                 is_throw[3]=1;
239                 dfs();
240                 w[a[3].loca]=t1;
241                 w[i]=t2;
242                 a[3].loca=t3;
243                 is_throw[3]=t4;
244             }
245 
246         }
247     }
248 }
249 
250 int dfs(){
251     ans=max(ans,a[1].loca);
252     ans=max(ans,a[2].loca);
253     ans=max(ans,a[3].loca);
254     //if(is_move[1]==1&&is_move[2]==1&&is_move[3]==1&&is_throw[1]==1&&is_throw[2]==1&&is_throw[3]==0||is_throw[1]==1&&is_throw[2]==0&&is_throw[3]==1||is_throw[1]==0&&is_throw[2]==1&&is_throw[3]==1){
255     //    return 0;
256     //}else{
257         for(int i=1;i<=9;i++){
258             if(!step[i]){
259                 switch(i){
260                 case 1:step[1]=1;fun11();step[1]=0;break;
261                 case 2:step[2]=1;fun12();step[2]=0;break;
262                 case 3:step[3]=1;fun13();step[3]=0;break;
263                 case 4:step[4]=1;fun21();step[4]=0;break;
264                 case 5:step[5]=1;fun22();step[5]=0;break;
265                 case 6:step[6]=1;fun23();step[6]=0;break;
266                 case 7:step[7]=1;fun31();step[7]=0;break;
267                 case 8:step[8]=1;fun32();step[8]=0;break;
268                 case 9:step[9]=1;fun33();step[9]=0;break;
269                 }
270             }
271 
272         }
273         return 0;
274     //}
275 
276 }
277 
278 int main()
279 {
280     for(int i=1;i<=3;i++){
281         scanf("%d %d %d",&a[i].loca,&a[i].moverange,&a[i].throwrange);
282     }
283     dfs();
284     printf("%d\n",ans);
285     return 0;
286 }