农夫在x位置,下一秒可以到x-1, x+1, 2x,问最少多少步可以到k
*解法:最少步数bfs
要注意的细节蛮多的,写在注释里了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
queue<int> q;
int vis[], arr[];
void go(int n, int k)
{
q.push(n);
vis[n] = ;
int flag = ;
while(!q.empty())
{
if(flag) break;
int head = q.front(); q.pop();
int direct[] = {, -, head};
if(head == k) return;
for(int i = ; i < ; i++)
{
int next = head + direct[i];
if(next >= && next <= && !vis[next])//坐标一共有1e5但是可以移动到2x 所以next<=2e5;然后next可能小于0,vis[next]直接RE,所以把vis[next]放在最后,先判next>= 0
{
q.push(next);
vis[next] = ;
arr[next] = arr[head] + ;
}
if(next == k) flag = ;
}
}
return;
}
int main()
{
int n, k;
while(scanf("%d %d", &n, &k) != EOF)
{
while(!q.empty()) q.pop();
memset(vis, , sizeof(vis));
memset(arr, , sizeof(arr));
go(n, k);
printf("%d\n", arr[k]);
}
return ;
}

最新文章

  1. redis之理解
  2. unrecognized selector sent to instance
  3. 最后一次PSP
  4. dbstart和dbshut启动、关闭数据库报错ORACLE_HOME_LISTNER is not SET解决办法
  5. Hadoop Shell命令字典(可收藏)
  6. BZOJ1016 最小生成树计数
  7. 理解Java中的接口
  8. C++编程中const和#define的区别
  9. 关于无限分类的树状输出(id,name,pid)类型的
  10. python与数值计算环境搭建
  11. POJ 2449 Remmarguts&#39; Date (SPFA + A星算法) - from lanshui_Yang
  12. 工作流Jpbm4.4工作流知识点总结(工作流开发宝典)
  13. CentOS 7 安装Subversion, 并用Nginx代理
  14. How does exercise keep your brain young?
  15. Scala学习笔记(七):Rational、隐式转换、偏函数、闭包、重复参数及柯里化
  16. 采用xtrabackup部署主从同步
  17. web页面中快速找到html对应元素两种方法
  18. db2 MON_GET_PKG_CACHE_STMT 表函数 抓取分析SQL
  19. mongodb丢失数据的原因剖析 - 迎风飘来的专栏 - CSDN博客 https://blog.csdn.net/yibing548/article/details/50844310
  20. Django框架----命名URL和URL反向解析

热门文章

  1. E20180430-hm
  2. C++开发工程师面试题库 50~100道
  3. HDOJ2955 0/1背包的价值和重量
  4. hdoj1260【简单DP】
  5. c#删除指定文件夹中今天之前的文件
  6. 2017zstu新生赛
  7. sql 语句操作,修改字段中字符串的一部分
  8. java自带线程池
  9. Keepalived+LVS(DR)+MySQL
  10. .NET Core WebAPI Swagger使用