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 wocha at 2012-10-29 20:27:43 on Problem 3414
#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:
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