本文共 2939 字，大约阅读时间需要 9 分钟。

一、题目：

就是告诉你和一头牛的位置，牛是不动的，问你最多走几步可以抓住这头牛。

走步有3种方式：

1. 向前走1步（step + 1）

2. 向后走1步（step - 1）

3. 步数乘2.（step * 2）

二、广搜的一般步骤：

void bfs(起始点) {    将起点放入队列中;    标记起点访问;    while (如果队列不为空) {        访问队首元素x;        删除队首元素;        for (x 所有的相邻点) {            if (该点未被访问过且合法) {                将该点加入队列;                标记该点访问过;            }        }    队列为空，广搜结束。}

三、代码：

#include 
   
    #include 
    
     using namespace std;queue
     
      
        > q;bool vis[100005];const int max_num = 1e5;int main() {    int N, K, now, step;    scanf("%d%d", &N, &K);    q.push(make_pair(N, 0));        //加入队首元素    vis[N] = true;                  //标记队首元素已访问    while (!q.empty()) {        now = q.front().first;        //取出队首元素信息，这里是now和step        step = q.front().second;        q.pop();                    //取出队首信息后，出队        if (now == K) {            //若满足条件，结束循环            printf("%d\n", step);            break;        }        if (now + 1 <= max_num && !vis[now + 1]) {    //若合法，则广搜            q.push(make_pair(now + 1, step + 1));            vis[now + 1] = true;        }        if (now - 1 >= 0 && !vis[now - 1]) {            q.push(make_pair(now - 1, step + 1));    //若合法，则广搜            vis[now - 1] = true;        }        if (now * 2 <= max_num && !vis[now * 2]) {    //若合法，则广搜            q.push(make_pair(now * 2, step + 1));            vis[now * 2] = true;        }    }    return 0;}
      
     
    
   

四、思考：

看了计蒜客的视频讲解后，我得到了下面的一些思考：

1. BFS用的是队列，不像DFS一样是递归的过程，所以可以直接放在主函数来写。
2. 如果有T组数据，一定要清空队列queue。
3. 有vis数组后，时间复杂度最差为O(n)，即把所有的情况都访问一遍。
4. 可以在判断now+ 1,now - 1 ,now * 2合法和是否访问过时直接判断这个数是不是想要的结果。如果是直接输出step+ 1，这样可以不用把它加入队列，节省很多时间。（我在下面试了这个方法，可以奏效，但是这里还需要特判一下是不是N == K，如果是则直接输出0，否则会WA。不过总体来讲，时间降得很厉害，效率很高，直接由16ms降到了0ms）。下面可以看到效果：

五、更新后的代码：

#include 
   
    #include 
    
     using namespace std;queue
     
      
        > q;bool vis[100005];const int max_num = 1e5;int main() {    int N, K, now, step;    scanf("%d%d", &N, &K);    if (N == K) {            //需要特判一下，否则N==K结果会是2        printf("0\n");        return 0;    }    q.push(make_pair(N, 0));    while (!q.empty()) {        now = q.front().first;        step = q.front().second;        q.pop();        if (now + 1 <= max_num && !vis[now + 1]) {            if (now + 1 == K) {                //若条件合法，且没有访问过，我们就看看是不是我们想要的数，如果是直接输出结果加1即可。                printf("%d\n", step + 1);                break;            }            q.push(make_pair(now + 1, step + 1));            vis[now + 1] = true;        }        if (now - 1 >= 0 && !vis[now - 1]) {            if (now - 1 == K) {                printf("%d\n", step + 1);                break;            }            q.push(make_pair(now - 1, step + 1));            vis[now - 1] = true;        }        if (now * 2 <= max_num && !vis[now * 2]) {            if (now * 2 == K) {                printf("%d\n", step + 1);                break;            }            q.push(make_pair(now * 2, step + 1));            vis[now * 2] = true;        }    }    return 0;}
      
     
    
   

转载地址：http://nqwn.baihongyu.com/