| ||||||||||
| 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