Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

仔细点就好

Posted by 984597422 at 2018-04-30 21:14:08 on Problem 3414
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator