越看越像动态规划

原题链接：8049.抓住那头牛

bits/stdc++.h

2024-09-05 18:22:59

发布于：广东

17阅读

0回复

0点赞

动归有人会做吗

有帮助，赞一个

去预览

0/2000

全部评论 5

Macw07
不可以用动态规划。vis 数组会开很大，没有办法记忆化搜索。

2024-09-06 来自加拿大
0
‮队团加不）ด้้童帅_者仇复
可以移动到 $X-1$ ，应该算有后效性吧，不能用动归

2024-09-05 来自广东
0

零

AI回答②：

Python 题解

from collections import deque

def minTimeToCatchCow(N, K):
    if N >= K:
        return N - K  # 特殊情况：N >= K，直接向左移动

    visited = [False] * 100001  # 记录访问状态
    queue = deque([(N, 0)])  # 队列，存储当前位置和时间
    visited[N] = True

    while queue:
        pos, time = queue.popleft()

        if pos == K:
            return time  # 找到目标位置

        # 三种移动方式
        if pos - 1 >= 0 and not visited[pos - 1]:
            queue.append((pos - 1, time + 1))
            visited[pos - 1] = True

        if pos + 1 <= 100000 and not visited[pos + 1]:
            queue.append((pos + 1, time + 1))
            visited[pos + 1] = True

        if pos * 2 <= 100000 and not visited[pos * 2]:
            queue.append((pos * 2, time + 1))
            visited[pos * 2] = True

    return -1  # 正常情况下不会执行到这里

# 输入与输出
N, K = map(int, input().split())
print(minTimeToCatchCow(N, K))

解释

特殊情况：如果 N >= K，农夫只需要向左移动即可，这样耗时就是 N - K。
广度优先搜索 (BFS)：每次都从当前位置尝试三种移动方式，并记录已经访问过的位置，以避免重复计算。只要找到目标位置 K，输出对应的时间即可。

这两种解法的时间复杂度均为 O(100000)，因为每个位置最多访问一次，空间复杂度也是 O(100000)。

2024-09-05 来自浙江

零

AI回答①：

这道题目描述的是一个典型的双向广度优先搜索（BFS）问题，农夫需要最少时间从位置 N 移动到位置 K 抓住牛，移动方式包括向前、向后以及通过瞬移移动到当前点的两倍位置。

思路

用一个队列来进行广度优先搜索（BFS），队列中存储当前位置和到达该位置所花费的时间。
从初始位置 N 开始，尝试使用三种移动方式：
- 向前移动一格（x + 1），耗时1分钟；
- 向后移动一格（x - 1），耗时1分钟；
- 瞬移到两倍位置（2 * x），耗时1分钟。
使用一个数组或集合记录访问过的节点，防止重复访问，优化时间复杂度。
每次从队列中取出一个位置，查看它是否是目标位置 K，如果是则输出当前时间作为结果。

C++ 题解

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int minTimeToCatchCow(int N, int K) {
    if (N >= K) return N - K;  // 特殊情况：N >= K，直接向左移动

    vector<int> visited(100001, 0);  // 记录访问状态
    queue<pair<int, int>> q;  // 队列，存储当前位置和时间
    q.push({N, 0});  // 初始位置和时间为0
    visited[N] = 1;

    while (!q.empty()) {
        int pos = q.front().first;
        int time = q.front().second;
        q.pop();

        if (pos == K) return time;  // 找到目标位置

        // 三种移动方式
        if (pos - 1 >= 0 && !visited[pos - 1]) {
            q.push({pos - 1, time + 1});
            visited[pos - 1] = 1;
        }
        if (pos + 1 <= 100000 && !visited[pos + 1]) {
            q.push({pos + 1, time + 1});
            visited[pos + 1] = 1;
        }
        if (pos * 2 <= 100000 && !visited[pos * 2]) {
            q.push({pos * 2, time + 1});
            visited[pos * 2] = 1;
        }
    }

    return -1;  // 正常情况下不会执行到这里
}

int main() {
    int N, K;
    cin >> N >> K;
    cout << minTimeToCatchCow(N, K) << endl;
    return 0;
}