时间戳

首页 > 技术文章 > 抓住那头牛_BFS

抓住那头牛_BFS

rongrongrong 2022-02-11 14:21 原文

1100. 抓住那头牛

农夫知道一头牛的位置，想要抓住它。

农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。

农夫有两种移动方式：

  1. 从 X 移动到 X−1 或 X+1，每次移动花费一分钟
  2. 从 X 移动到 2∗X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。

农夫最少要花多少时间才能抓住牛？

输入格式

共一行，包含两个整数N和K。

输出格式

输出一个整数，表示抓到牛所花费的最少时间。

数据范围

0 ≤ N , K ≤ 10 ^ 5

输入样例：

5 17

输出样例：

4

思路：

　　DFS的话超时，找最短路径这类问题还得是BFS；

　　具体思路见表：

　　如样例  n = 5 k = 17：

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
q[i] 5 6 10 4 7 12 11 20 9 8 3 14 13 24 22 19 18 16 2 15 28 26 23 21 17 32 1 30 27 25
dist[q[i]] 0 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, k;
int dist[2 * N];
int q[N];

int bfs(){
    memset(dist, -1, sizeof(dist));
    q[0] = n;
    dist[n] = 0;
    int hh = 0, tt = 0;
    while(hh <= tt){
        int t = q[hh++];
        
        if(t == k)  return dist[t];
        
        if(t + 1 <= k && dist[t + 1] == -1){
            q[++tt] = t + 1;
            dist[t + 1] = dist[t] + 1;
        }
        if(t * 2 <= 2 * k && dist[t * 2] == -1){
            q[++tt] = t * 2;
            dist[t * 2] = dist[t] + 1;
        }
        if(t - 1 >= 0 && dist[t - 1] == -1){
            q[++tt] = t - 1;
            dist[t - 1] = dist[t] + 1;
        }
    }
    
}
int main()
{
    cin >> n >> k;
    
    cout << bfs() << endl;
    
    return 0;
}

推荐阅读