USACO备考冲刺必刷题 | P1588 Catch That Cow S

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 x 和 y，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 2×x 的位置。计算他至少需要几步追上他的牛。

【输入】

第一行为一个整数 t (1≤t≤10)，表示数据组数；

接下来每行包含一个两个正整数 x,y (0<x,y≤105)，分别表示 FJ 和牛的坐标。

【输出】

对于每组数据，输出最少步数。

【输入样例】

1 
5 17

【输出样例】

4

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int t, x, y;
int vis[100005]={0}, d[100005]={0};  // vis数组用来标记该点是否来过，d数组用来表示到达该点的步数
int main()
{
    cin >> t;  // 输入t组
    while (t--) {  // 依次接受t组数据输入并处理
        cin >> x >> y;  // 输入x和y
        queue<int> q;  // 定义队列
        memset(vis, 0, sizeof(vis));  // 初始化vis和d数组
        memset(d, 0, sizeof(d));
        if (x==y) {  // 如果x与y重合
            cout << 0 << endl;  // 说明牛和FJ在同一个位置，输出为0
        }
        if (x>y) {  // 如果x大于y
            cout << x-y << endl;  // 则只能向后退，步数为x-y
        }
        if (x < y) {  // 如果x小于y，则使用广搜
            int tp = x;  // 定义tp为x坐标
            vis[tp] = 1;  // 标记该点已经访问过
            q.push(tp);  // 压入队列中
            while (!q.empty()) {  // 如果队列不为空
                int tp = q.front();  // 取出队头
                q.pop();
                if (tp==y) {  // 广搜退出条件，即tp与y重合
                    cout << d[tp] << endl;  // 打印d[tp]，即到达tp这个点的步数
                    break;  // 退出循环，无需继续搜索
                }
                if (vis[tp+1]!=1 && tp+1>=0 && tp+1<=100000) {  // 对前进一步的位置进行边界判断及访问情况判断，符合条件再继续
                    q.push(tp+1);  // 前进一步位置压入队列
                    vis[tp+1] = 1;  // 标记为访问过
                    d[tp+1] = d[tp] + 1;  // 更新到达前进一步的步数
                }
                if (vis[tp-1]!=1 && tp-1>=0 && tp-1<=100000) {  // 对后退一步的位置进行边界判断及访问情况判断
                    q.push(tp-1);  // 后退一步位置压入队列
                    vis[tp-1] = 1;  // 标记为访问过
                    d[tp-1] = d[tp] + 1;  // 更新到达后退一步的步数
                }
                if (vis[tp*2]!=1 && tp*2>=0 && tp*2<=100000) {  // 对2*x的位置进行边界判断及访问情况判断
                    q.push(tp*2);  // 2*x位置压入队列
                    vis[tp*2] = 1;  // 标记为访问过
                    d[tp*2] = d[tp] + 1;  // 更新2*x位置的步数
                }
            }
        } 
    }
    return 0;
}

【运行结果】

1 
5 17
4