题解：P1588 [USACO07OPEN] Catch That Cow S

Zhc0731 · 2025-07-13 21:41:07 · 题解

BFS搜索

前置芝士

广搜怎么写：

先把起点放到队列里，在一直循环直到队列元素为空（所有点都遍历完才会这样），取出当前队列中的元素（就是当前位置），从当前位置遍历所有从当前位置可以到的位置，把这个位置放到队列中…………如果有一次取出队列元素（及当前位置）等于终点，就直接输出从起点到这个点的步数

解题思路

这道题一看就是广搜

这个题需要用结构体，来存每一个点的位置和步数，从起点开始延伸，遇到没有走过的点就加入队列。

如果一个点位置等于牛的位置，输出步数

否则判断现在的坐标是否比牛的坐标大，如果大的话就只要往后走一步，因为往前走没有意义，如果小于等于的话，就前进一步、后退一步或者直接走到 2×x 的位置，这农夫是人吗

代码

#include<bits/stdc++.h>
using namespace std;
int x, y;
int ans = 0;
struct node{
    long long zb, step;//每一个点的位置和步数
};
int main(){
    int tp;
    cin >> tp;
    while(tp--){
        ans = 0;
        cin >> x >> y;
        queue<node>q;
        q.push({x, 0});//存入农夫初始位置，步数为0
        bool vis[max(x, y) * 2] = {0};//这样就不用重置了
        while(q.size()){
            node t = q.front();
            q.pop();//把第一个点拿出来
            if(t.zb == y){//如果一个点位置等于牛的位置
                cout << t.step << endl;//输出步数
                break;
            }
            if(t.zb > y){//判断现在的坐标是否比牛的坐标大
                int nx = t.zb - 1;//后退一步
                if(nx >= 0 && !vis[nx]){//判断是否为没有走过的点和有没有越界
                    vis[nx] = 1;
                    q.push({nx, t.step + 1});//如果大的话就只要往后走一步
                }
            }else{
                int nx = t.zb - 1;//后退一步
                if(nx >= 0 && !vis[nx]){//判断是否为没有走过的点和有没有越界
                    vis[nx] = 1;
                    q.push({nx, t.step + 1});
                }
                nx = t.zb * 2;//直接走到 2x 的位置
                if(nx<=y && !vis[nx]){//判断是否为没有走过的点和有没有越界
                    vis[nx] = 1;
                    q.push({nx, t.step + 1});
                }
                nx = t.zb + 1;//前进一步
                if(nx<=y && !vis[nx]){//判断是否为没有走过的点和有没有越界
                    vis[nx] = 1;
                    q.push({nx, t.step + 1});
                }
            }
        }
    }
    return 0;
}