POJ - 3278 Catch That Cow bfs 线性

时间:2021-03-29 14:30:43
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int a[],vis[];
queue<int>q; int bfs(int n,int k)
{
int head,next,i;
q.push(n);
a[n]=;
vis[n]=;
while(q.size()!=)
{
head=q.front();
q.pop();
for(i=;i<;i++)
{
if(i==)next=head-;
else if(i==)next=head+;
else if(i==)next=head*;
if(next>=&&next<=)
{
if(vis[next]==)
{
q.push(next);
a[next]=a[head]+;
vis[next]=;
}
if(next==k)
return a[next];
}
}
} }
int main()
{
int i,j,n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(a,,sizeof(a));
memset(vis,,sizeof(vis));
while(!q.empty())q.pop();
if(n>=k)
printf("%d\n",n-k);
else
{
printf("%d\n",bfs(n,k));
}
}
return ;
}