1100. 抓住那头牛题解

题目描述

avatar avatar

解题思路

数组要开2倍的1e5, 因为k最大可以在1e5,所以2 * n < 2 * 1e5

对于第一种走法,只有在+1后不越界N时才可以对于第二种走法,只有在-1后不为负数才可以对于第三种走法,只有在*2后不越界才可以

以上三种情况需要开一个dist[][]记录距离,这个数组同时也可以记录某个位置是否被访问过由于是求最短路,所以可以用BFS对这三种情况进行搜索

代码

cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 200020;
int n, k;
int dist[N];

int bfs()
{
    queue<int>q;
    q.push(n);
    
    memset(dist, -1, sizeof dist);
    dist[n] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop();
        
        if (t == k) return dist[k];  // 搜到终点了就直接返回
        
        if (t + 1 < N && dist[t + 1] == -1)  
        {
            dist[t + 1] = dist[t] + 1;
            q.push(t + 1);
        }
        if (t - 1 >= 0 && dist[t - 1] == -1)
        {
            dist[t - 1] = dist[t] + 1;
            q.push(t - 1);
        }
        if (t * 2 < N && dist[t * 2] == -1)
        {
            dist[t * 2] = dist[t] + 1;
            q.push(t * 2);
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d", &n, &k);
    
    printf("%d", bfs());
    return 0;
}

题目描述 ​

解题思路 ​

代码 ​

题目描述

解题思路

代码