| ||||||||||
| 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 | |||||||||
用Strig存操作include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
int a,b,c;
int v[111][111];
struct node
{
int x;
int y;
int step;
string s;
};
int bfs()
{
queue<node>Q;
int l=1;
node p,q;
p.x=0;
p.y=0;
p.step=0;
p.s+='0';
Q.push(p);
v[0][0]=1;
while(!Q.empty())
{
p=Q.front();
Q.pop();
//printf("%d %d %d ",p.x,p.y,p.step);
//cout<<p.s<<endl;
if(p.x==c||p.y==c)
{
cout<<p.step<<endl;
for(int i=0; p.s[i]!='\0'; i++)
{
if(p.s[i]=='1')
{
printf("FILL(1)\n");
}
if(p.s[i]=='2')
{
printf("DROP(1)\n");
}
if(p.s[i]=='3')
{
printf("POUR(1,2)\n");
}
if(p.s[i]=='4')
{
printf("FILL(2)\n");
}
if(p.s[i]=='5')
{
printf("DROP(2)\n");
}
if(p.s[i]=='6')
{
printf("POUR(2,1)\n");
}
}
return 1;
}
else
{
int xx=a,yy=b;
q.x=p.x+(xx-p.x); // 把 1 倒满 记为 1
q.y=p.y;
q.s=p.s+'1';
q.step=p.step+1;
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
q.x=0; //把 1 倒掉 记为 2
q.y=p.y;
q.s=p.s+'2';
q.step=p.step+1;
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
if(p.x>=(yy-p.y)) // 把1倒给2 记为 3
{
q.x=p.x-(yy-p.y);
q.y=p.y+(yy-p.y);
q.step=p.step+1;
q.s=p.s+'3';
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
}
if(p.x<yy-p.y) // 把1倒给2 记为 3
{
q.x=0;
q.y=p.y+p.x;
q.step=p.step+1;
q.s=p.s+'3';
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
}
q.x=p.x; // 把2倒满 记为 4
q.y=p.y+(yy-p.y);
q.s=p.s+'4';
q.step=p.step+1;
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
q.x=p.x; //把2倒掉 记为 5
q.y=0;
q.s=p.s+'5';
q.step=p.step+1;
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
if(p.y>=(xx-p.x)) //把2倒给1 记为 6
{
q.x=p.x+(xx-p.x);
q.y=p.y-(xx-p.x);
q.s=p.s+'6';
q.step=p.step+1;
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
}
else if(p.y<xx-p.x)
{
q.x=p.x+p.y;
q.y=0;
q.s=p.s+'6';
q.step=p.step+1;
if(v[q.x][q.y]==0)
{
v[q.x][q.y]=1;
Q.push(q);
}
}
}
}
return 0;
}
int main()
{
while(~scanf("%d %d %d",&a,&b,&c))
{
memset(v,0,sizeof(v));
int sum=bfs();
if(sum==0)
printf("impossible\n");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator