pku 3278 Catch That Cow－－－BFS

poj 3278(bfs)
题目很简单，bfs直接可以解决掉，注意截枝：有些位置前面已经出现了，后面就不用重复了。
设了一个tag[]帮助解决这个问题。
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include <queue>
#define Len 100005
using namespace std;

struct Node
{
     int x;
  int step;
};
bool tag[Len];
int main()
{
 queue<Node> q;
 int n,k,x,step,ans;
 Node cur;
 scanf("%d%d",&n,&k);
 
  ans=0;
  memset(tag,0,sizeof(tag));
  cur.x=n;
  cur.step=0;
  tag[n]=1;
  q.push(cur);

  while(!tag[k])//bfs
  {

   cur=q.front();
   q.pop();
   x=cur.x;
   step=cur.step;
   if(x-1>=0&&!tag[x-1])//截枝，是否超出界限？前面是否访问过此点？
   {
    
    tag[x-1]=1;
    cur.x=x-1;
    cur.step=step+1;//前一步的时间+1,
    q.push(cur);
    if(x-1==k)
    {
     ans=step+1;
     break;
    }
   }
   if(x+1<Len&&!tag[x+1])
   {
    tag[x+1]=1;
    cur.x=x+1;
    cur.step=step+1;
    q.push(cur);
    if(x+1==k)
    {
     ans=step+1;
     break;
    }
   }
   if(x*2<Len&&!tag[x*2])
   {
    tag[x*2]=1;
    cur.x=2*x;
    cur.step=step+1;
    q.push(cur);
    if(2*x==k)
    {
     ans=step+1;
     break;
    }
   }
  }
 printf("%d/n",ans);
  
 

return 0;
}

最后

以上就是动人墨镜为你收集整理的pku 3278 Catch That Cow－－－BFS的全部内容，希望文章能够帮你解决pku 3278 Catch That Cow－－－BFS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。