题目： http://poj.org/problem?id=3414
很好玩的一个题。关键是又16ms 1A了，没有debug的日子才是好日子。。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
int a, b, c;
bool vis[][];
enum Ways{FILL_A, FILL_B, DROP_A, DROP_B, POUR_AB, POUR_BA}; struct Path
{
int px, py;
Ways way;
}path[][]; struct status
{
int x, y, step;
}; void print_path(int x, int y)
{
stack<struct Path>s;
while(!(x == && y == ))
{
s.push(path[x][y]);
int tx = path[x][y].px;
int ty = path[x][y].py;
x = tx;
y = ty;
}
while(!s.empty())
{
switch(s.top().way)
{
case FILL_A: printf("FILL(1)\n");break;
case FILL_B: printf("FILL(2)\n");break;
case DROP_A: printf("DROP(1)\n");break;
case DROP_B: printf("DROP(2)\n");break;
case POUR_AB: printf("POUR(1,2)\n");break;
case POUR_BA: printf("POUR(2,1)\n");break;
}
s.pop();
}
} queue<struct status>q;
void bfs()
{
while(!q.empty())
{
struct status u = q.front();
q.pop();
if(u.x == c || u.y == c)
{
printf("%d\n", u.step);
print_path(u.x, u.y);
return;
} if(u.x < a && !vis[a][u.y])
{
q.push((struct status){a, u.y, u.step+});
vis[a][u.y] = ;
path[a][u.y] = (struct Path){u.x, u.y, FILL_A};
} if(u.y < b && !vis[u.x][b])
{
q.push((struct status){u.x, b, u.step+});
vis[u.x][b] = ;
path[u.x][b] = (struct Path){u.x, u.y, FILL_B};
} if(u.x > && !vis[][u.y])
{
q.push((struct status){, u.y, u.step+});
vis[][u.y] = ;
path[][u.y] = (struct Path){u.x, u.y, DROP_A};
} if(u.y > && !vis[u.x][])
{
q.push((struct status){u.x, , u.step+});
vis[u.x][] = ;
path[u.x][] = (struct Path){u.x, u.y, DROP_B};
} if(u.x > && u.y < b)
{
int tmp = min(u.x, b-u.y);
if(!vis[u.x-tmp][u.y+tmp])
{
q.push((struct status){u.x-tmp, u.y+tmp, u.step+});
vis[u.x-tmp][u.y+tmp] = ;
path[u.x-tmp][u.y+tmp] = (struct Path){u.x, u.y, POUR_AB};
}
} if(u.x < a && u.y > )
{
int tmp = min(a-u.x, u.y);
if(!vis[u.x+tmp][u.y-tmp])
{
q.push((struct status){u.x+tmp, u.y-tmp, u.step+});
vis[u.x+tmp][u.y-tmp] = ;
path[u.x+tmp][u.y-tmp] = (struct Path){u.x, u.y, POUR_BA};
}
}
}
printf("impossible\n");
} int main()
{
scanf("%d %d %d", &a, &b, &c);
memset(vis, , sizeof(vis));
q.push((struct status){, , });
vis[][] = ;
bfs();
return ;
}