P1588 [USACO07OPEN] Catch That Cow S 洛谷 BFS-最短路思想

news/2025/1/2 3:11:40/

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1

1 
5 17

输出 #1

4
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;// 定义常量 N,用于数组大小的定义,确保数组足够大以容纳可能的最大值
const int N = 2e5 + 10 + 2e5;// 全局变量声明
int n, k; // n 和 k 分别表示起始位置和目标位置
int d;    // 测试用例的数量
int q[N]; // 队列,用于广度优先搜索 (BFS) 的节点存储
int dist[N]; // 记录从起点到每个点的距离/*** bfs 函数:使用广度优先搜索算法计算从起点 n 到终点 k 的最短距离。* * @return 返回从起点 n 到终点 k 的最短距离,如果无法到达则返回 -1。*/
int bfs()
{// 初始化距离数组,所有位置初始设为 -1 表示未访问memset(dist, -1, sizeof(dist));// 起点 n 的距离设为 0dist[n] = 0;// 将起点加入队列q[0] = n;// 队列的头指针 hh 和尾指针 tt 初始化为 0int hh = 0, tt = 0;// 当队列不为空时继续搜索while (hh <= tt){// 取出队列头部元素int t = q[hh++];// 如果当前节点是目标节点 k,返回其距离if (t == k) return dist[t];// 检查并处理 t+1 这个位置if (t + 1 <= k && dist[t + 1] == -1) {// 更新距离并将其加入队列dist[t + 1] = dist[t] + 1;q[++tt] = t + 1;}// 检查并处理 t-1 这个位置if (t - 1 >= 0 && dist[t - 1] == -1){// 更新距离并将其加入队列dist[t - 1] = dist[t] + 1;q[++tt] = t - 1;}// 检查并处理 t*2 这个位置if (t * 2 < N && dist[t * 2] == -1){// 更新距离并将其加入队列dist[t * 2] = dist[t] + 1;q[++tt] = t * 2;}}// 如果遍历完所有可达节点仍未找到目标节点 k,返回 -1return -1;
}/*** main 函数:程序入口,读取输入并调用 bfs 函数计算结果。*/
int main()
{// 读取测试用例数量 dcin >> d;// 对每个测试用例进行处理while (d--){// 读取起点 n 和目标位置 kcin >> n >> k;// 调用 bfs 函数计算最短距离并输出结果cout << bfs() << endl;}return 0;
}

 

 


http://www.ppmy.cn/news/1559237.html

相关文章

计算机专业考研 408 学科学习方法

计算机专业考研 408 学科涵盖数据结构、计算机组成原理、操作系统和计算机网络四门核心课程&#xff0c;内容多且难度大。但只要掌握科学的学习方法&#xff0c;便能化繁为简&#xff0c;稳步提升。以下为大家详细介绍 408 学科的学习方法。 一、基础夯实阶段&#xff1a;全面…

Pytorch | 利用MIG针对CIFAR10上的ResNet分类器进行对抗攻击

Pytorch | 利用MIG针对CIFAR10上的ResNet分类器进行对抗攻击 CIFAR数据集MIG介绍算法流程 MIG代码实现MIG算法实现攻击效果 代码汇总mig.pytrain.pyadvtest.py 之前已经针对CIFAR10训练了多种分类器&#xff1a; Pytorch | 从零构建AlexNet对CIFAR10进行分类 Pytorch | 从零构建…

【每日学点鸿蒙知识】屏幕高度、证书签名、深色模式对上架影响、Taskpool上下文、List触底加载更多

1、HarmonyOS 关于屏幕高度&#xff1f; display.getDefaultDisplaySync 可以获取到整个屏幕的高度&#xff0c; 那顶部的状态栏和底部的安全区高度 怎么获取&#xff1f; 可以在EntryAbility里获取并存储,获取到的高度是px&#xff0c;所以用px2vp&#xff08;&#xff09;转…

ip归属地怎么判定?如何查看自己ip属地

在当今数字化时代&#xff0c;IP地址作为互联网通信的基础&#xff0c;扮演着至关重要的角色。而IP归属地的判定与查看&#xff0c;不仅关乎网络安全、隐私保护&#xff0c;还直接影响到社交平台的信任机制与信息传播的真实性。本文将深入探讨IP归属地的判定原理以及如何查看自…

JAVA开发初级入门之-如何快速将Java开发环境搭建,优雅草央千澈快速IDEA与JDK安装配置环境教程一文让你搞定-java开发必修课之一

JAVA开发初级入门之-如何快速将Java开发环境搭建&#xff0c;优雅草央千澈快速IDEA与JDK安装配置环境教程一文让你搞定-java开发必修课之一 软件准备 idea&#xff08;IntelliJ IDEA&#xff09; 知识扩展&#xff1a; IntelliJ IDEA 是由 JetBrains 开发的一款广泛使用的集成开…

论文浅尝 | 编辑基于语言模型的知识图谱嵌入(AAAI2024)

笔记整理&#xff1a;曲晏林&#xff0c;天津大学硕士&#xff0c;研究方向为大语言模型 论文链接&#xff1a;https://arxiv.org/abs/2301.10405 发表会议&#xff1a;AAAI 2024 1. 动机 知识图谱(Knowledge Group, KG)由三元组(头部实体、关系、尾部实体)组成&#xff0c;广泛…

Day56 图论part06

108.冗余连接 并查集应用类题目,关键是如何把题意转化成并查集问题 代码随想录 import java.util.Scanner;public class Main{public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();DisJoint disjoint = new DisJo…

【漫话机器学习系列】021.类别特征(Categorical Feature)

类别特征&#xff08;Categorical Feature&#xff09; 类别特征&#xff08;Categorical Feature&#xff09;是指取值为有限的、不连续的类别或标签的数据特征。在机器学习和数据分析中&#xff0c;类别特征经常用于描述对象的分类属性&#xff0c;例如颜色、性别、职业等。…