poj 3278 Catch That Cow-搜索进阶-暑假集训
Catch That Cow
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
Output
Sample Input
5 17
Sample Output
4
Hint
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<stack>
using namespace std;
#define N 100010
int time[N], maps[N], s, e;//将这些宏定义是为了避免传参;
void BFS();
int main()
{
while(scanf("%d%d", &s, &e)!=EOF)
{
memset(time, 0, sizeof(time));//定义的时间数组,初始化为零;本身定义了结构体,其中包含了位置location、时间time、标记变量flag。却发现flag无法初始化
memset(maps, 0, sizeof(maps));//标记是否走过
if(s==e)
printf("0\n");
else
BFS();
}
return 0;
}
void BFS()
{
queue<int>que;
int i, x, dir;
maps[s]=1;
que.push(s);
while(!que.empty())
{
x=que.front();
que.pop();
for(i=0; i<3; i++)
{
switch(i)//用switch更简便;
{
case 0: dir=x-1; break;
case 1: dir=x+1; break;
case 2: dir=x*2; break;
}
if(dir==e)//结束条件。其实也可放在for循环外,只不过是多进行了几步而已
{
printf("%d\n", time[x]+1);
return;
}
if(maps[dir]==0&&dir<N&&dir>=0)//这也算是剪枝,减少了重复
{
que.push(dir);
maps[dir]=1;
time[dir]=time[x]+1;
}
}
}
}
最新文章
- 存储程序(1)——MYSQL
- 使用page object模式抓取几个主要城市的pm2.5并从小到大排序后写入txt文档
- MVC中的BASE.ONACTIONEXECUTING(FILTERCONTEXT) 的作用
- c指针与数组,传参问题,指针数组与数组指针的区别,二维数组动态内存分配
- js Module模式
- poj 2240 Arbitrage (Floyd)
- android 50 进程优先级
- 服务器端javascript——Rhino和Node
- 【iOS】Resumable Doanloads(断点下载)
- Android的AsyncTask类的解读
- MVC EF 增 删 改 查
- PAT (Advanced Level) 1021. Deepest Root (25)
- Android开发之AsyncTask示例Demo
- vs 修改活动解决方案配置后无法调试,不生成pdb文件,“当前不会命中断点 还没有为该文档加载任何符号” 解决方法
- CF527E Data Center Drama(构造+欧拉回路)
- bitnami下webmin安装
- python测试开发django-19.admin后台自定义显示
- DWZ主从表界面唯一性验证(自写js)(一)
- OpenACC parallel
- 微信小程序 --01
热门文章
- Android 完整开源应用大全,完整开源项目
- nginx限速
- 【Linux 驱动】设备驱动程序再理解
- Atitit.跨语言&#160;java&#160;c#.net&#160;php&#160;js常用的codec&#160;encode算法api&#160;兼容性&#160;&#160;应该内置到语言里面
- [转]Ubuntu Server命令行更换软件源
- 为什么jdbc中的resultset只能取一次去第二次就报错了
- busybox下inittab中runlevel解析
- nginx proxy_pass 里的”/”
- 在ListView的GroupItem头中显示每列的Summary
- mac地址绑定