zoj 1005 Jugs BFS

感想：这是我的第一道oj题，思路我想了很久，感觉建模能力还是不够强啊，理清楚了就好，把各个操作看成一条路，BFS就好

http://acm.zju.edu.cn/onlinejudge/showPRoblem.do?problemCode=1005

#include<iostream>#include<stdio.h>#include<algorithm>#include<string>#include<stack>#include<map>#include<vector>#include<deque>using namespace std;string s[7]={"fill A","fill B","empty A","empty B","pour A B","pour B A","success"}; vector<string> t;struct jugs {	int AT;	int BT;}; deque<jugs> de;int A,B,N;int main(){	while(scanf("%d %d %d",&A,&B,&N)!=EOF){		int *isread=new int[(A+2)*(B+2)];		int *a=new int[(A+2)*(B+2)];		int *c=new int[(A+2)*(B+2)];		jugs em,temp1,temp2;		em.AT=0;		em.BT=0;		isread[0*B+0]=1;		de.clear();		de.push_back(em);		while(!de.empty()){			temp1=de.front();			de.pop_front();			if(isread[A*(B+1)+temp1.BT]==0){				temp2=temp1;				temp2.AT=A;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=0;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}			if(isread[temp1.AT*(B+1)+B]==0){				temp2=temp1;				temp2.BT=B;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=1;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}			if(isread[temp1.AT+temp1.BT]==0&&temp1.AT+temp1.BT<=B){				temp2.AT=0;				temp2.BT=temp1.AT+temp1.BT;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=4;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}			if(temp1.AT+temp1.BT>B&&isread[(temp1.AT-B+temp1.BT)*(B+1)+B]==0){				temp2.AT=temp1.AT-B+temp1.BT;				temp2.BT=B;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=4;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}			if(temp1.AT+temp1.BT>A&&isread[A*(B+1)+(temp1.BT-A+temp1.AT)]==0){				temp2.AT=A;				temp2.BT=temp1.BT-A+temp1.AT;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=5;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}			if(isread[(temp1.AT+temp1.BT)*(B+1)]==0&&temp1.AT+temp1.BT<=A){				temp2.BT=0;				temp2.AT=temp1.AT+temp1.BT;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=5;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}			if(isread[temp1.BT]==0){				temp2.AT=0;				temp2.BT=temp1.BT;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=2;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}			if(isread[temp1.AT*(B+1)]==0){				temp2.BT=0;				temp2.AT=temp1.AT;				a[temp2.AT*(B+1)+temp2.BT]=temp1.AT*(B+1)+temp1.BT;				c[temp2.AT*(B+1)+temp2.BT]=3;				if(temp2.BT==N)				break;				de.push_back(temp2);				isread[temp2.AT*(B+1)+temp2.BT]=1;			}		}		int tt=temp2.AT*(B+1)+temp2.BT;		t.clear();		while(tt!=0){			t.push_back(s[c[tt]]);			tt=a[tt];		}		for(int i=t.size()-1;i>=0;i--){			cout<<t[i]<<endl;		}		cout<<"success"<<endl;	}}