【搜索算法】练习二：poj3278 Catch That Cow、poj1426 Find The Multiple

poj3278 Catch That Cow

题目链接：https://vjudge.net/problem/POJ-3278

1.题目描述

  Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

  Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute   Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

  If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

2.输入要求

  Line 1: Two space-separated integers: N and K

3.输出要求

  Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

4.题目解释

  农夫约翰已被告知一头逃犯的位置，并希望立即将其抓住。他开始于一个点Ñ（0≤ Ñ在数轴上≤100,000）和母牛是在点ķ（0≤ ķ上相同数目的线≤100,000）。农夫约翰有两种运输方式：步行和传送。

  行走：FJ可以在一分钟内从任意点X移至点X -1或X + 1。   传送：FJ可以在一分钟内从任意点X移至点2× X。

  如果没有意识到它的追捕能力的母牛完全没有动弹，那么农夫约翰要花多长时间才能找回它？

5.测试样例

Sample Input
5 17

Sample Output
4

6.代码

#include
#include
#include
using namespace std;

//n,k最大为100000
#define N 200001
bool visit[N];
int n,k;

//结构体，点和步数
struct node{
    int id;
    int step;
};

//广度优先遍历
int bfs(int n,int k)
{
    queue q;
    node f;
    //初始化
    f.id = n;
    f.step = 0;
    visit[n] = true;
    q.push(f);
    while(!q.empty())
    {
        node now = q.front();
        q.pop();
        if(now.id==k) return now.step;
        //分别遍历三种情况
        node next;
        for(int i=0;i>n>>k;
    memset(visit,false,sizeof(visit));
    cout