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 |
POJ测试数据确实很边缘化,用100*100的数组就是过不了,上代码#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<stack> using namespace std; bool map[105][105]; char op[6][15]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"}; int a,b,c; struct point { int x,y; int step; }; struct point2 { int fx,fy; int oper; }; point2 opera[105][105]; point fill1(point t) { point temp; temp.x=a; temp.y=t.y; temp.step=t.step+1; return temp; } point fill2(point t) { point temp; temp.x=t.x; temp.y=b; temp.step=t.step+1; return temp; } point drop1(point t) { point temp; temp.x=0; temp.y=t.y; temp.step=t.step+1; return temp; } point drop2(point t) { point temp; temp.x=t.x; temp.y=0; temp.step=t.step+1; return temp; } point pour1(point t) { point temp; if(t.x+t.y>=b) { temp.y=b; temp.x=t.x+t.y-b; } else { temp.y=t.x+t.y; temp.x=0; } temp.step=t.step+1; return temp; } point pour2(point t) { point temp; if(t.x+t.y>=a) { temp.x=a; temp.y=t.x+t.y-a; } else { temp.x=t.x+t.y; temp.y=0; } temp.step=t.step+1; return temp; } int main() { queue<point> q; while(scanf("%d%d%d",&a,&b,&c)!=EOF) { memset(map,0,sizeof(map)); memset(opera,0,sizeof(opera)); bool p=false; point p1; p1.x=0; p1.y=0; p1.step=0; q.push(p1); map[0][0]=true; while(!q.empty()) { point temp1=q.front(); q.pop(); if(temp1.x==c||temp1.y==c) { p=true; printf("%d\n",temp1.step); stack<int> s; point temp; temp.x=temp1.x; temp.y=temp1.y; while(temp.x||temp.y) { s.push(opera[temp.x][temp.y].oper); int t1=temp.x; int t2=temp.y; temp.x=opera[t1][t2].fx; temp.y=opera[t1][t2].fy; } while(!s.empty()) { int temp2=s.top(); s.pop(); printf("%s\n",op[temp2]); } break; } point temp[6]; temp[0]=fill1(temp1); temp[1]=fill2(temp1); temp[2]=drop1(temp1); temp[3]=drop2(temp1); temp[4]=pour1(temp1); temp[5]=pour2(temp1); for(int i=0;i<6;i++) { if(!map[temp[i].x][temp[i].y]) { opera[temp[i].x][temp[i].y].fx=temp1.x; opera[temp[i].x][temp[i].y].fy=temp1.y; opera[temp[i].x][temp[i].y].oper=i; map[temp[i].x][temp[i].y]=true; q.push(temp[i]); } } } if(!p) printf("impossible\n"); while(!q.empty()) q.pop(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator