| ||||||||||
| 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 <iostream>
#include <queue>
#include <cstring>
using namespace std;
int a, b, c;
bool ava = false;
bool vis[101][101];
struct tree
{
tree* father;
int op;
tree(tree* father, int op) : father(father), op(op) {}
};
struct node
{
int a;
int b;
tree* t;
};
queue<node> q;
tree* bfs()
{
while(!q.empty())
{
tree *father = q.front().t;
int anow = q.front().a;
int bnow = q.front().b;
q.pop();
node n;
for(int i = 0; i < 6; i++)
{
int anext = anow;
int bnext = bnow;
switch(i)
{
case 0:
{
if(anow < a)
{
anext = a;
}
break;
}
case 1:
{
if(anow)
{
anext = 0;
}
break;
}
case 2:
{
if(anow)
{
if(anow + bnow <= b)
{
bnext = anow + bnow;
anext = 0;
}
else
{
anext = anow + bnow - b;
bnext = b;
}
}
break;
}
case 3:
{
if(bnow < b)
{
bnext = b;
}
break;
}
case 4:
{
if(bnow)
{
bnext = 0;
}
break;
}
case 5:
{
if(bnow)
{
if(anow + bnow <= a)
{
anext = anow + bnow;
bnext = 0;
}
else
{
bnext = anow + bnow - a;
anext = a;
}
}
break;
}
}
if(!vis[anext][bnext])
{
vis[anext][bnext] = true;
node n;
n.a = anext;
n.b = bnext;
n.t = new tree(father, i);
if(anext == c || bnext == c)
{
ava = true;
return n.t;
}
q.push(n);
}
}
}
return NULL;
}
string findd(int n)
{
switch(n)
{
case 0:
return "FILL(1)";
case 1:
return "DROP(1)";
case 2:
return "POUR(1,2)";
case 3:
return "FILL(2)";
case 4:
return "DROP(2)";
case 5:
return "POUR(2,1)";
}
}
void outPut(tree *t, int n)
{
if(t->father == NULL)
{
cout << n << endl;
cout << findd(t->op) << endl;
return;
}
outPut(t->father, n + 1);
cout << findd(t->op) << endl;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
memset(vis, false, sizeof(vis));
vis[0][0] = true;
cin >> a >> b >> c;
if(c == a)
{
cout << 1 << endl;
cout << "FILL(1)" << endl;
return 0;
}
else if(c == b)
{
cout << 1 << endl;
cout << "FILL(2)" << endl;
return 0;
}
while(!q.empty())
{
q.pop();
}
node n;
n.a = a;
n.b = 0;
n.t = new tree(NULL, 0);
q.push(n);
n.b = b;
n.a = 0;
n.t = new tree(NULL, 3);
q.push(n);
vis[0][b] = true;
vis[a][0] = true;
tree* t = bfs();
if(!ava)
{
cout << "impossible";
}
else
{
outPut(t, 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