Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
BFS 16ms。。。附代码,有详细备注!!!!!!!!!!!!#include<iostream> #include<cstring> using namespace std; struct AB { int pre;//指向前一状态(前一状态数组下标) int a,b; int c;//通过第几个操作得到当前状态 }; AB q[10050];//存储状态 int head,tail; int A,B,C; int aa,bb;//当前两桶里的水 bool visit[101][101];//A,B<=100,所以有100*100种状态,判断此状态是否访问过。 void FILL(int i) { if(i==1) aa=A; else bb=B; } void POUR(int i,int j) { int a=aa,b=bb; if(i==1) { if(a+b>B) { bb=B; aa=a+b-B; } else { bb=a+b; aa=0; } } else { if(a+b>A) { aa=A; bb=a+b-A; } else { aa=a+b; bb=0; } } } void DROP(int i) { if(i==1) aa=0; else bb=0; } void operate(int i) { switch(i) { case 0: { FILL(1); break; } case 1: { FILL(2); break; } case 2: { POUR(1,2); break; } case 3: { POUR(2,1); break; } case 4: { DROP(1); break; } case 5: { DROP(2); break; } } } void out(int i) { switch(i) { case 0: { cout<<"FILL(1)"<<endl; break; } case 1: { cout<<"FILL(2)"<<endl; break; } case 2: { cout<<"POUR(1,2)"<<endl; break; } case 3: { cout<<"POUR(2,1)"<<endl; break; } case 4: { cout<<"DROP(1)"<<endl; break; } case 5: { cout<<"DROP(2)"<<endl; break; } } } int BFS() { head=tail=0; q[tail].a=0; q[tail].b=0; q[tail++].pre=-1;//标记该状态为起始点 visit[0][0]=true; while(true) { if(head==tail) { return 0;//队列为空,未找到目标状态,无解 } if(q[head].a==C||q[head].b==C) { return head;//返回目标状态下标 } for(int i=0; i<6; i++) { aa=q[head].a; bb=q[head].b;//读取当前状态 operate(i);//计算操作i之后的状态 if(!visit[aa][bb])//如果此状态未访问 { visit[aa][bb]=true; q[tail].pre=head;//由当前状态产生的状态,所以pre指向当前状态 q[tail].a=aa; q[tail].b=bb; q[tail++].c=i;//记录操作i } } head++; } } int main() { cin>>A>>B>>C; memset(visit,false,sizeof(visit)); int t=BFS(); int way[10000],n=0; if(!t) cout<<"impossible"<<endl; else { while(q[t].pre!=-1)//统计到达目标状态所经过状态个数(初始状态不算)并记录状态下标 { //状态数组中只有指向前一状态,无法正向输出,将状态下标记录到way[]中进行倒序输出; way[n++]=t; t=q[t].pre; } cout<<n<<endl; while(n--) { out(q[way[n]].c); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator