| ||||||||||
| 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 | |||||||||
贴个代码!!!!#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <cstdio>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <new>
#include <set>
#define inf 0x3f3f3f3f
#define M 1006
#define stop system("pause")
using namespace std;
int vis[M][M];
struct node {
int aleft;
int bleft;
int step;
};
struct pre{
int num;
int operat;
} next[M];
void prin(int x){
x=next[x].num;
if(x==-1) return;
else prin (x);
if(next[x].operat==1) puts("FILL(1)");
else if(next[x].operat==2) puts("FILL(2)");
else if(next[x].operat==3) puts("DROP(1)");
else if(next[x].operat==4) puts("DROP(2)");
else if(next[x].operat==5) puts("POUR(1,2)");
else if(next[x].operat==6) puts("POUR(2,1)");
}
void bfs(int A,int B,int C){
queue<node> q;
node t,p,temp;
int f=0;
t.aleft=0;
t.bleft=0;
t.step=0;
int head=0,tail=1;
next[0].num=-1;
memset(vis,0,sizeof(vis));
vis[t.aleft][t.bleft]=1;
q.push(t);
while(!q.empty()){
p=q.front();
q.pop();
if(p.aleft==C || p.bleft==C ) {
printf("%d\n",p.step);
int u=head;
prin(head);
if(next[u].operat==1) puts("FILL(1)");
else if(next[u].operat==2) puts("FILL(2)");
else if(next[u].operat==3) puts("DROP(1)");
else if(next[u].operat==4) puts("DROP(2)");
else if(next[u].operat==5) puts("POUR(1,2)");
else if(next[u].operat==6) puts("POUR(2,1)");
f=1;
return ;
}
for(int i=1;i<=7;i++){
if(i==1){ //fill a
if(p.aleft!=A&&!vis[A][p.bleft]){
vis[A][p.bleft]=1;
temp.aleft=A;
temp.bleft=p.bleft;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
}
} else if(i==2){ //fill b
if(p.bleft!=B&&!vis[p.aleft][B]){
vis[p.aleft][B]=1;
temp.aleft=p.aleft;
temp.bleft=B;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
}
} else if(i==3){ //drop a;
if(p.aleft&&!vis[0][p.bleft]){
vis[0][p.bleft]=1;
temp.aleft=0;
temp.bleft=p.bleft;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
}
} else if(i==4){ //drop b;
if(p.bleft&&!vis[p.aleft][0]){
vis[p.aleft][0]=1;
temp.bleft=0;
temp.aleft=p.aleft;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
}
} else if(i==5){ // pour(1,2)
if(p.bleft!=B&&p.aleft){
if(p.aleft>B-p.bleft&&!vis[p.aleft-B+p.bleft][B]){
vis[p.aleft-B+p.bleft][B]=1;
temp.aleft=p.aleft-B+p.bleft;
temp.bleft=B;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
} else if(p.aleft<=B-p.bleft&&!vis[0][p.bleft+p.aleft]){
vis[0][p.bleft+p.aleft]=1;
temp.aleft=0;
temp.bleft=p.bleft+p.aleft;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
}
}
} else if(i==6){ //pour (2,1)
if(p.aleft!=A&&p.bleft){
if(p.bleft>A-p.aleft&&!vis[A][p.bleft-A+p.aleft]){
vis[A][p.bleft-A+p.aleft]=1;
temp.aleft=A;
temp.bleft=p.bleft-A+p.aleft;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
} else if(p.bleft<=A-p.aleft&&!vis[p.aleft+p.bleft][0]){
vis[p.aleft+p.bleft][0]=1;
temp.bleft=0;
temp.aleft=p.bleft+p.aleft;
temp.step=p.step+1;
next[tail].num=head;
next[tail++].operat=i;
q.push(temp);
}
}
}
}
head++;
}
if(f==0) puts("impossible");
}
int main(){
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c))
bfs(a,b,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