| ||||||||||
| 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 | |||||||||
哪位大神给看看一直RE什么情况#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#define N 106
#define met(a, b) memset (a, b, sizeof (a))
typedef long long LL;
//const int INF = ((1<<31)-1);
struct node
{
int prea, preb, op;
}pots[N][N];
struct node1
{
int a, b, step;
bool friend operator < (const node1 &a, const node1 &b)
{
return a.step > b.step;
}
}pre, p;
int vis[N][N], a, b, c, flag, path[N*20000];
node1 BFS ()
{
priority_queue <node1> que;
pre.a = pre.b = pre.step = 0;
pots[0][0].prea = pots[0][0].preb = pots[0][0].op = 0;
met (vis, 0);
vis[0][0] = 1;
que.push (pre);
while (que.size())
{
pre = que.top(); que.pop();
if (pre.a == c || pre.b == c)
{
flag = 1;
return pre;
}
for (int i=1; i<=6; i++)
{
if (i == 1)//FILL(a)
{
p.a = a;
p.b = pre.b;
}
else if (i == 2)//FILL(b)
{
p.a = pre.a;
p.b = b;
}
else if (i == 3)//DROP(a)
{
p.a = 0;
p.b = pre.b;
}
else if (i == 4)//DROP(b)
{
p.a = pre.a;
p.b = 0;
}
else if (i == 5)//POUR(a, b)
{
if (pre.b + pre.a > b)
{
p.a = pre.a - (b-pre.b);
p.b = b;
}
else
{
p.a = 0;
p.b = pre.a + pre.b;
}
}
else//POUR(b, a)
{
if (pre.a + pre.b > a)
{
p.a = a;
p.b = pre.b - (a-pre.a);
}
else
{
p.a = pre.a + pre.b;
p.b = 0;
}
}
if (!vis[p.a][p.b])
{
vis[p.a][p.b] = 1;
p.step = pre.step + 1;
pots[p.a][p.b].prea = pre.a;
pots[p.a][p.b].preb = pre.b;
pots[p.a][p.b].op = i;
que.push (p);
}
}
}
}
int main ()
{
node1 ans;
int i, x, y, step;
while (scanf ("%d %d %d", &a, &b, &c) != EOF)
{
met (path, 0);
flag = 0;
ans = BFS ();
if (!flag)
{
puts ("impossible");
continue;
}
printf ("%d\n", ans.step);
step = ans.step;
x = ans.a, y = ans.b;
for (i=step; i>=1; i--)
{
path[i] = pots[x][y].op;
int xx = x;
x = pots[xx][y].prea;
y = pots[xx][y].preb;
}
for (i=1; i<=step; i++)
{
if (path[i] == 1) puts ("FILL(1)");
if (path[i] == 2) puts ("FILL(2)");
if (path[i] == 3) puts ("DROP(1)");
if (path[i] == 4) puts ("DROP(2)");
if (path[i] == 5) puts ("POUR(1,2)");
if (path[i] == 6) puts ("POUR(2,1)");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator