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