| ||||||||||
| 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 | |||||||||
BFS+回溯打印 自我感觉代码还是蛮漂亮的(让各位见笑了。。)#include <cstdio>
#include <cstring>
#include <queue>
#define N 111
#define S 99
#define D1 -1
#define D2 -2
#define F1 1
#define F2 2
#define P12 12
#define P21 21
using namespace std;
class Path
{
public:
int x;
int y;
};
class State
{
public:
int x;
int y;
int k;
State(){}
State(int initx,int inity,int initk)
:x(initx),y(inity),k(initk){}
};
int A,B,C;
int v[N][N];
Path path[N][N];
queue<State> q;
void Init()
{
memset(v,0,sizeof(v));
}
void Next(int x,int y,State cur,int mode)
{
if(!v[x][y])
{
v[x][y] = mode;
path[x][y].x = cur.x;
path[x][y].y = cur.y;
q.push(State(x,y,cur.k+1));
}
}
State BFS()
{
v[0][0] = S;
path[0][0].x = -1;
path[0][0].y = -1;
q.push(State(0,0,0));
State cur;
while(q.size())
{
cur = q.front();
q.pop();
if(cur.x==C||cur.y==C)
{
while(q.size())
{
q.pop();
}
return cur;
}
Next(0,cur.y,cur,D1);
Next(cur.x,0,cur,D2);
Next(A,cur.y,cur,F1);
Next(cur.x,B,cur,F2);
int rx = A - cur.x;
int ry = B - cur.y;
if(cur.x<=ry)
{
Next(0,cur.y+cur.x,cur,P12);
}
else
{
Next(cur.x-ry,B,cur,P12);
}
if(cur.y<=rx)
{
Next(cur.x+cur.y,0,cur,P21);
}
else
{
Next(A,cur.y-rx,cur,P21);
}
}
return State(-1,-1,-1);
}
void PrintPath(int x,int y,int k)
{
if(!k)
{
return;
}
PrintPath(path[x][y].x,path[x][y].y,k-1);
switch(v[x][y])
{
case D1:
printf("DROP(1)\n");
break;
case D2:
printf("DROP(2)\n");
break;
case F1:
printf("FILL(1)\n");
break;
case F2:
printf("FILL(2)\n");
break;
case P12:
printf("POUR(1,2)\n");
break;
case P21:
printf("POUR(2,1)\n");
break;
}
}
int main()
{
Init();
scanf("%d %d %d",&A,&B,&C);
State ret = BFS();
if(ret.k==-1)
{
printf("impossible\n");
}
else
{
printf("%d\n",ret.k);
PrintPath(ret.x,ret.y,ret.k);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator