首页 > 其他分享 >kuangbin专题一 简单搜索 抓住那头牛(POJ-3278)

kuangbin专题一 简单搜索 抓住那头牛(POJ-3278)

时间:2023-04-14 20:34:35浏览次数:55  
标签:typedef John dist int Farmer POJ kuangbin include 3278

Catch That Cow

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 210291 Accepted: 63838

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

  • Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
  • Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.



题目大意

给一个起始点 N 和终点 K , 假设当前位置为 X , 有三种移动方式,第一种是往左走一个单位长度,即变成 X - 1 ; 第二种是往右走一个单位长度,即变成 X + 1 ; 第三种是从 X 变成 2 * X 。 每种移动方式消耗的时间都是一分钟。求得从起始点到终点的最短耗费时间。



解题思路

这道题很简单,就是在一个X轴上的BFS求最短路模型,只要按照思路写就行。

/*   一切都是命运石之门的选择  El Psy Kongroo  */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, pii> psi;
typedef __int128 int128;
#define x first
#define y second
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;

const int N = 1e5 + 10;
int sx, tx;    //起点 终点
int dist[N];

//判断位置是否合法
bool check(int x){
    return x >= 0 && x < N && dist[x] == -1;  
}

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

    while(!q.empty()){
        int x = q.front();
        q.pop();

        if(x == tx) return dist[x];   //到达终点

        if(check(x - 1)) q.push(x - 1), dist[x - 1] = dist[x] + 1;
        if(check(x + 1)) q.push(x + 1), dist[x + 1] = dist[x] + 1;
        if(check(2 * x)) q.push(2 * x), dist[2 * x] = dist[x] + 1;
    }

    return -1;
}

int main(){
    cin >> sx >> tx;
    int res = bfs();

    cout << res << endl;

    return 0;
}

标签:typedef,John,dist,int,Farmer,POJ,kuangbin,include,3278
From: https://www.cnblogs.com/MAKISE004/p/17319845.html

相关文章

  • kuangbin专题一 简单搜索 棋盘问题(POJ-1321)
    棋盘问题TimeLimit:1000MS MemoryLimit:10000KTotalSubmissions:125427 Accepted:56304Description在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘......
  • kuangbin专题一 简单搜索 地牢大师(POJ-2251)
    DungeonMasterTimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:92499 Accepted:31990DescriptionYouaretrappedina3Ddungeonandneedtofindthequickestwayout!Thedungeoniscomposedofunitcubeswhichmayormaynotbefilledwith......
  • POJ 1780 Code (欧拉回路+非递归版dfs)
    题目地址:POJ1780还是求序列的欧拉回路。只不过这题有两坑。第一坑是用数字来当点的话,会MLE,因为每个数字可以连10条边,100w条边会MLE,即使用vector也会TLE。这题可以用边来记录,对于n为1时直接输出,然后后面的,比如12,23这两个点就用边权值为123来表示这两个点,这样就把点和边的范围......
  • HDU 1116 && POJ 1386 Play on Words(欧拉路径)
    按字母来建边,每个单词的首字母和尾字母加边。先判断是否连通,然后判断每个字母的入度和出度不能出现差的绝对值大于2,然后入度和出度差的绝对值为1的不能超过两个。就可以形成欧拉路径代码如下:#include<iostream>#include<string.h>#include<math.h>#include<queue>#include......
  • POJ 1753 Flip Game (高斯消元)
    题目地址:POJ1753第三次做这道题了。第一次是刚学搜索的时候做的,第二次是刚学状态压缩枚举的时候做的,这次是刚学高斯消元、、每次都做得很艰辛。。目测这题应该没了别的方法了吧。。。。。。这题除了高斯消元外还需要枚举变元,方法是状态压缩枚举,然后返回去迭代解方程。代码如下:#inc......
  • POJ 1830 开关问题 (高斯消元)
    题目地址:POJ1830高斯消元第一发。一个地方逻辑判断出现了失误,调了一下午啊。。。通过高斯消元来找矩阵的秩,然后2^(自由元的数量)就是答案。因为对于每个自由元,都有0和1两种状态可选。代码如下:#include<iostream>#include<string.h>#include<math.h>#include<queue>#includ......
  • POJ 2337 Catenyms (欧拉回路+并查集)
    题目地址:POJ2337这题跟POJ1386差不多,只不过这题多一个输出路径而已。按字母来建边,每个单词的首字母和尾字母加边。先判断是否连通,然后判断每个字母的入度和出度不能出现差的绝对值大于2,然后入度和出度差的绝对值为1的不能超过两个。就可以形成欧拉路径代码如下:#include<iostream......
  • POJ 1905 Expanding Rods (二分+计算几何+精度处理)
    题目地址:POJ1905用二分枚举h,然后判断弧长是否符合条件。重点还是在精度问题上,具体看代码吧。。#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include......
  • POJ 2299 Ultra-QuickSort(线段树+离散化)
    题目地址:POJ2299这题曾经用归并排序做过,线段树加上离散化也可以做。一般线段树的话会超时。这题的数字最大到10^10次方,显然太大,但是可以利用下标,下标总共只有50w。可以从数字大的开始向树上加点,然后统计下标比它小即在它左边的数的个数。因为每加一个数的时候,比该数大的数已经加完......
  • POJ 3468 A Simple Problem with Integers(线段树区间更新)
    题目地址:POJ3468打了个篮球回来果然神经有点冲动。。无脑的狂交了8次WA。。居然是更新的时候把r-l写成了l-r。。。这题就是区间更新裸题。区间更新就是加一个lazy标记,延迟标记,只有向下查询的时候才将lazy标记向下更新。其他的均按线段树的来就行。代码如下:#include<iostream>#in......