POJ3278 Catch That Cow(BFS) 坑爹的RE

2024-06-09 04:18
文章标签 cow bfs catch re 坑爹 poj3278

本文主要是介绍POJ3278 Catch That Cow(BFS) 坑爹的RE,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Catch That Cow

Time Limit: 2000MS Memory Limit: 65536K
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?**

InputLine 1: Two space-separated integers: N and K
OutputLine 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input5 17
Sample Output4
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(0≤N≤100000)处开始,母牛在同一数轴上的点K(0≤K≤10000)。 农夫有两种交通方式:步行和传送。
农夫可以前(当前坐标+1)后(当前坐标-1)行走或者传送(当前坐标*2),每次移动消耗一个单位时间,问追上奶牛的最短时间。

简单的BFS题,但是有很多坑,一不小心就RE。
以下是代码实现。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
bool vis[100010];
int n,k;
struct node{
int x;
int time;
};
int  bfs()
{  node q;
q.x=n;q.time=0;queue<node>p;p.push(q);vis[n]=1;
while(!p.empty())
{node tmp=p.front();p.pop();if(tmp.x==k)
{return tmp.time;
}for(int i=0;i<3;i++){ int xx;if(i==0)xx=tmp.x-1;else if(i==1)xx=tmp.x+1;elsexx=tmp.x*2;if(xx>100005|| xx<0 )  continue;//坑点,没有判断容易数组越界,若超过则进行下一次循环if(!vis[xx]){node nx;nx.x=xx;vis[xx]=1;nx.time=tmp.time+1;p.push(nx);}}}return -1;//这行不能丢,虽然题目没给出要求
}int main()
{memset(vis,0,sizeof(vis));scanf("%ld%ld",&n,&k);//使用%ldif(n>=k){printf("%d",n-k);//若农夫在奶牛前面,则直接回退}else{printf("%d",bfs());}return 0;
}

这篇关于POJ3278 Catch That Cow(BFS) 坑爹的RE的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1044194

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

C++第四十七弹---深入理解异常机制:try, catch, throw全面解析

✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】【C++详解】 目录 1.C语言传统的处理错误的方式 2.C++异常概念 3. 异常的使用 3.1 异常的抛出和捕获 3.2 异常的重新抛出 3.3 异常安全 3.4 异常规范 4.自定义异常体系 5.C++标准库的异常体系 1.C语言传统的处理错误的方式 传统的错误处理机制:

双头BFS

牛客月赛100 D题,过了80%数据,调了一下午。。。烦死了。。。 还是没调试出来,别人的代码用5维的距离的更新有滞后性,要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx

try -catch-finally的理解,同时在try-catch-finally中含有return和throws的理解

在没有try-catch或try-catch-finally的情况下,程序正常执行到某行,在这行报错后,这行后面的代码就不执行了,程序就停止了,中断了。 例如   在有try-catch或try-catch-finally 情况上,在某行执行错误,在try中这行下的代码不执行,try外的代码执行。当然是catch在没有做处理的情况下。如果catch中做了处理,在不影响当前程序下,try

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<

hdu2717(裸bfs广搜)

Catch That Cow Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7304 Accepted Submission(s): 2308 题目链接: http://acm.hdu.edu.cn/showproblem.