| ||||||||||
| 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 | |||||||||
哪位大牛能帮我改改路径输出,小弟我已经在此纠结了好久了,就是不明白为什么用函数递归出不来路径~~~#include <iostream>
#include <queue>
using namespace std;
struct point
{
int a,b;
int t;
int step;
point * pre;
};
bool vis[103][103];
char str[6][10]={"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
int a,b,c,ta,tb;
point now;
int bfs();
void print(point now)
{
if(now.pre!=NULL)
print(*now.pre);
cout<<str[now.t]<<endl;
};
int main()
{
while(cin>>a>>b>>c)
{
memset(vis,false,sizeof(vis));
cout<<bfs()<<endl;
}
return 0;
}
int bfs()
{
queue<point>q;
point start,node;
start.a=0;
start.b=0;
start.step=0;
start.pre=NULL;
q.push(start);
int step,x,y;
while (!q.empty())
{
start=q.front();
q.pop();
x=start.a;
y=start.b;
step=start.step;
if(x==c||y==c) { print(start);return step;}
for(int i=0;i<6;i++)
{
if(i==0)
{ ta=a;tb=y;}
if(i==1)
{ ta=x;tb=b;}
if(i==2)
{ ta=0;tb=y;}
if(i==3)
{ ta=x;tb=0;}
if(i==4)
{ if(b-y>=x)
{ ta=0;tb=x+y; }
else
{ ta=x+y-b;tb=b; }
}
if(i==5)
{ if(a-x>=y)
{ ta=x+y;tb=0; }
else
{ ta=a; tb=x+y-a; }
}
if(!vis[ta][tb])
{
node.a=ta;
node.b=tb;
node.t=i;
node.step=step+1;
node.pre=&start;
q.push(node);
vis[ta][tb]=true;
}
}
}
cout << "impossible" << endl;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator