POJ-3278.CatchThatCow(数字BFS最短路输出)
2024-08-28 21:51:51
本题大意:一个农夫和一头牛在一个数轴上,牛不动,农夫每次可使自己的坐标 +1 , -1, *2 ,问最小需要多少次农夫与牛坐标相等。
本题思路:最短路,BFS。
本题代码:
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
using namespace std; int n, k, ans;
const int maxn = 1e5 + , INF = -;
int step[maxn];
bool vis[maxn];
int bfs() {
int now, Next;
queue <int> s;
s.push(n);
step[n] = ;
vis[n] = true;
while(!s.empty()) {
now = s.front();
s.pop();
for(int i = ; i < ; i ++) {
if(i == )
Next = now - ;
else if(i == )
Next = now + ;
else
Next = now * ;
if(Next < || Next >= maxn) continue;
if(!vis[Next]) {
step[Next] = step[now] + ;
s.push(Next);
vis[Next] = true;
}
if(Next == k) return step[Next];
}
}
return -;
} int main () {
memset(vis, false, sizeof(vis));
memset(step, , sizeof(step));
scanf("%d %d", &n, &k);
ans = bfs();
printf("%d\n", ans);
return ;
}
最新文章
- 查询表结构sql
- CSS3的透明度使用
- rabbitMQ第四篇:远程调用
- Javascript 笔记与总结(2-4)Javascript 内置对象
- jboss4.2.3禁用http put/delete等请求
- 通过email分享
- mybatis实战教程(mybatis in action)之九:mybatis 代码生成工具的使用
- 解决outlook无法启动
- Math.random与java.util.Random的差别
- WebApp中调试jsavascript
- 记vue API 知识点
- 服务器开发之CGI后门
- Python实现微信消息防撤回
- DAX/PowerBI系列 - 关于时间系列 - 时间相关数值比较 - 用非自带函数
- linux 基本原则和常用命令
- 2.2 if语句
- 09-OpenLDAP加密传输配置
- 使用promise 和 generator来管理工作流
- codeforces 848B Rooter&#39;s Song 思维题
- 把旧系统迁移到.Net Core 2.0 日记(9) -- T4 Template