| ||||||||||
| 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<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int A,B,C;
struct NODE{
int index;
int a,b;
};
struct PUTID{
int way;
int pre_index;
}putid[10005];
int index;
bool mark;
bool visit[105][105];
bool judge(int a,int b){
if(a == C || b == C) return true;
return false;
}
int Max(int a,int b){
if(a > b) return a;
return b;
}
void OUTPUT(int index,int steps){
if(index == -1) return;
OUTPUT(putid[index].pre_index,steps + 1);
if(!mark){
printf("%d\n",steps);
mark = true;
}
switch(putid[index].way){
case 1:
printf("FILL(1)\n");
break;
case 2:
printf("FILL(2)\n");
break;
case 3:
printf("DROP(1)\n");
break;
case 4:
printf("DROP(2)\n");
break;
case 5:
printf("POUR(1,2)\n");
break;
case 6:
printf("POUR(2,1)\n");
break;
default:
break;
}
}
void CHKoutput(int a,int b,int way){
printf("%d %d WAY:",a,b);
switch(way){
case 1:
printf("FILL(1)\n");
break;
case 2:
printf("FILL(2)\n");
break;
case 3:
printf("DROP(1)\n");
break;
case 4:
printf("DROP(2)\n");
break;
case 5:
printf("POUR(1,2)\n");
break;
case 6:
printf("POUR(2,1)\n");
break;
default:
break;
}
}
int main()
{
while(~scanf("%d%d%d",&A,&B,&C))
{
if(C > Max(A,B)) continue;
struct NODE cur;
queue<NODE>q;
while(!q.empty()) q.pop();
memset(visit,false,sizeof(visit));
for(int i = 0;i <= 10005; ++i){
putid[i].way = 0;
putid[i].pre_index = -1;
}
mark = false;
index = 0;
cur.a = 0;
cur.b = 0;
cur.index = ++index;
putid[cur.index].pre_index = -1;
putid[cur.index].way = 0;
visit[cur.a][cur.b] = true;
q.push(cur);
while(!q.empty()){
cur = q.front();
q.pop();
//printf("%d %d WAY:%d\n",cur.a,cur.b,putid[cur.index].way);
NODE nxt;
if(cur.a != A){
nxt.a = A;
nxt.b = cur.b;
if(!visit[nxt.a][nxt.b]){
nxt.index = ++index;
putid[nxt.index].pre_index = cur.index;
putid[nxt.index].way = 1;
//CHKoutput(nxt.a,nxt.b,putid[nxt.index].way);
if(judge(nxt.a,nxt.b)){
OUTPUT(nxt.index,0);
break;
}
visit[nxt.a][nxt.b] = true;
q.push(nxt);
}
}
if(cur.b != B){
nxt.a = cur.a;
nxt.b = B;
if(!visit[nxt.a][nxt.b]){
nxt.index = ++index;
putid[nxt.index].pre_index = cur.index;
putid[nxt.index].way = 2;
//CHKoutput(nxt.a,nxt.b,putid[nxt.index].way);
if(judge(nxt.a,nxt.b)){
OUTPUT(nxt.index,0);
break;
}
visit[nxt.a][nxt.b] = true;
q.push(nxt);
}
}
if(cur.a != 0){
nxt.a = 0;
nxt.b = cur.b;
if(!visit[nxt.a][nxt.b]){
nxt.index = ++index;
putid[nxt.index].pre_index = cur.index;
putid[nxt.index].way = 3;
//CHKoutput(nxt.a,nxt.b,putid[nxt.index].way);
if(judge(nxt.a,nxt.b)){
OUTPUT(nxt.index,0);
break;
}
visit[nxt.a][nxt.b] = true;
q.push(nxt);
}
}
if(cur.b != 0){
nxt.a = cur.a;
nxt.b = 0;
if(!visit[nxt.a][nxt.b]){
nxt.index = ++index;
putid[nxt.index].pre_index = cur.index;
putid[nxt.index].way = 4;
//CHKoutput(nxt.a,nxt.b,putid[nxt.index].way);
if(judge(nxt.a,nxt.b)){
OUTPUT(nxt.index,0);
break;
}
visit[nxt.a][nxt.b] = true;
q.push(nxt);
}
}
if(cur.a != 0 && cur.b != B){
if(cur.a <= B - cur.b){
nxt.a = 0;
nxt.b = cur.b + cur.a;
}
else{
nxt.a = cur.a - (B - cur.b);
nxt.b = B;
}
if(!visit[nxt.a][nxt.b]){
nxt.index = ++index;
putid[nxt.index].pre_index = cur.index;
putid[nxt.index].way = 5;
//CHKoutput(nxt.a,nxt.b,putid[nxt.index].way);
if(judge(nxt.a,nxt.b)){
OUTPUT(nxt.index,0);
break;
}
visit[nxt.a][nxt.b] = true;
q.push(nxt);
}
}
if(cur.a != A && cur.b != 0){
if(cur.b <= A - cur.a){
nxt.a = cur.a + cur.b;
nxt.b = 0;
}
else{
nxt.a = A;
nxt.b = cur.b - (A - cur.a);
}
if(!visit[nxt.a][nxt.b]){
nxt.index = ++index;
putid[nxt.index].pre_index = cur.index;
putid[nxt.index].way = 6;
//CHKoutput(nxt.a,nxt.b,putid[nxt.index].way);
if(judge(nxt.a,nxt.b)){
OUTPUT(nxt.index,0);
break;
}
visit[nxt.a][nxt.b] = true;
q.push(nxt);
}
}
}
if(!mark) printf("impossible\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator