#include <iostream>#include <cmath>#include <cstring>using namespace std;#define M 50struct People{ int pos; bool lifted;//正在被举着 bool lifting;//正在举着别人 int lift;//举着的是谁 int maxmove;//最大移动距离 int maxthrow;//最大抛距离 bool hasmoved;//是否移动过 bool haslifted;//是否举过别人 //没有必要加上是否抛过别人的标记，因为只能举起别人一次}p[3];bool Pos[M];//数轴，作为标记是否某位置上有人 bool visit[10];//排序标记，有三个人且每个人有移动、举起、抛出三种状态，共有9种操作 int Max=0;//记录最大位置 void dfs(int k,int step){ int n = k / 3; //当前执行操作的人 int m = k % 3; //当前执行的动作 //move if(m==0) { if(p[n].lifted || p[n].lifting || p[n].hasmoved) return; int i=1; if(step == 9) i=p[n].maxmove;//最后一步，则直接向前移动最大距离 /*如果不是最后一步，那么他也不必从他能移动的最靠后的距离开始搜索 他只需要从 他的位置之前的 有人的位置 的前一个位置 开始搜索即可 如果他后面没人，那么他走的距离只需要从1开始搜索，不需要往后走，只需要往前走*/ else { for(int j=1;j<p[n].pos;j++) //从第一个位置到p[i]的当前位置遍历 { if(Pos[j])//找p[i]前面有人的位置，以此来判断移动距离 { int l = -(p[n].pos-j-1);//l为移动位置的 后一个位置 i= l<i?l:i; } } i = i > -p[n].maxmove ? i : -p[n].maxmove; //移动的距离不可以大于p[i]的最大移动距离 }//找出i---即最大移动多少步 for(;i <= p[n].maxmove; i++) { if(Pos[p[n].pos+i-1] || Pos[p[n].pos+i+1] || i==p[n].maxmove) //移动到的位置 的 前后有人，才可以进行举起抛出，才有意义 { if(p[n].pos+i >0 && !Pos[p[n].pos+i]) //不可以移动到数轴外，且移动的位置必须为空 { if(!i) continue;//i=0，表示不移动，进入下一个for循环 Pos[p[n].pos]=false;//当前位置置零 p[n].pos += i;//move i步 Pos[p[n].pos]=true;//move后的位置 置为1 p[n].hasmoved=true;//标记 Max= p[n].pos>Max ? p[n].pos : Max;//记录最大位置 //向下一步 深搜 for(int j=0;j<9;j++) { if(!visit[j]) { visit[j]=true; dfs(j,step+1); //向下一步 深搜 visit[j]=false;//回溯 } } //回溯 Pos[p[n].pos]=false; p[n].pos -= i; Pos[p[n].pos]=true; p[n].hasmoved=false; } } } } //lift else if(m==1) { if(p[n].lifted || p[n].lifting || p[n].haslifted) return; for(int i=0;i<3;i++) //找旁边的人，初始判断条件为两者距离为1 { if(abs(p[i].pos-p[n].pos) == 1) { if(p[i].lifted) continue;//如果这个人正被举着，则不能重复举起 //否者，标记相关信息 p[n].haslifted=true; p[n].lifting=true; p[n].lift=i; p[i].lifted=true; int temp=p[i].pos; //临时中间变量，以便回溯 Pos[p[i].pos]=false;//i被举起，则位置p[i].pos为空 p[i].pos=p[n].pos;//p[i]的位置即为p[n]的位置 //如果被举起的人i正在举着别人，则i举着的那个人的位置也要改变 if(p[i].lifting) { int j=p[i].lift;// j就是被i举着的人 p[j].pos=p[i].pos; } //继续搜索 for(int j=0;j<9;j++) { if(!visit[j]) { visit[j]=true; dfs(j,step+1);//向下一步深搜 visit[j]=false; } } //回溯（将一切标记过的或者改动过的还原） p[n].haslifted=false; p[n].lifting=false; p[n].lift= -1; p[i].lifted=false; p[i].pos=temp;//临时变量的作用即为 记下p[i]的原始位置，便于i还原 Pos[p[i].pos]=true; //p[i]举着的人j也要记得还原为 ：p[j]所被p[i]举着的位置 if(p[i].lifting) { int j=p[i].lift;// j就是被i举着的人 p[j].pos=p[i].pos; } } } } //throw else { if(!p[n].lifting || p[n].lifted) return; //如果这个人并没有举着别人，这或个人正被举着，则退出 int i=1; if(step == 9) i=p[n].maxthrow;//最后一步，直接向前抛出最大距离 else { for(int j=1;j<p[n].pos;j++) //从第一个位置到p[i]的当前位置遍历 { if(Pos[j])//找p[i]前面有人的位置，以此来判断抛出距离 { int l=-(p[n].pos-j-1);//l为抛出位置的 后一个位置 i=l<i?l:i; } } i= i> -p[n].maxthrow? i : -p[n].maxthrow; //抛出的距离不可以大于p[i]的最大抛出距离 }//找出i---即最大抛出多少步 for( ;i <= p[n].maxthrow; i++) { if(Pos[p[n].pos+i-1] || Pos[p[n].pos+i+1] || i == p[n].maxthrow) //抛出到的位置 的 前后为空，才有意义 { if(p[n].pos+i>0 && !Pos[p[n].pos+i]) //不可以抛出到数轴外，且抛出所到的位置必须为空 { int j=p[n].lift;//j为要被抛出的（即n举着的）人 p[j].pos += i;//j 被throw i步 Pos[p[j].pos]=true;//throw后的位置 置为1 p[n].lifting=false;//标记 p[n].lift = -1; p[j].lifted=false;//抛出后即为不再是被举起状态 Max= p[j].pos>Max ? p[j].pos : Max;//记录最大位置 //若被抛出的j的头顶上还举着人 if(p[j].lifting) { int k=p[j].lift;//k为被j举着的人 p[k].pos=p[j].pos;//k的位置与j位置同步 } //向下一步 深搜 for(int q=0;q<9;q++) { if(q == k) continue;// if(!visit[q]) { visit[q]=true; dfs(q,step+1); //向下一步 深搜 visit[q]=false;//回溯 } } //回溯 Pos[p[j].pos]=false; p[j].pos -= i; p[j].lifted=true; p[n].lift=j; p[n].lifting=true; if(p[j].lifting) { int k=p[j].lift; p[k].pos=p[j].pos; } } } } } }int main(){ memset(Pos, false, sizeof(Pos)); memset(visit, false, sizeof(visit)); //输入 for(int i = 0; i < 3; i++) { cin >> p[i].pos >> p[i].maxmove >> p[i].maxthrow; p[i].lifted = p[i].lifting = p[i].hasmoved = p[i].haslifted = false; p[i].lift = -1; Pos[p[i].pos] = true; } //深搜 for(int i = 0; i < 9; i++) { //一个合法的第一步，不可能是抛。必须先移动或者举起别人 if((i % 3) != 2) { visit[i] = true; dfs(i, 1); visit[i] = false;//回溯 } } //结果 cout << Max << endl; return 0;}
新闻热点
疑难解答
