POJ 3278 Catch That Cow 【BFS】

2019-11-08 03:26:05

字体：大中小

来源：转载

供稿：网友

题目链接：http://poj.org/PRoblem?id=3278 题意：假设一个人在位置x，那么他下一分钟能到达的位置是x-1,x+1,2*x，现给出你n,k，让你求从n到k最少所花费的时间解析：直接bfs

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>using namespace std;typedef long long ll;const int maxn = 1e6+100;int n,k;int vis[maxn];struct node{ int x,step; node() {} node(int _x,int _step) { x = _x; step = _step; }};int bfs(){ queue<node> q; memset(vis,0,sizeof(vis)); vis[n] = 1; q.push(node(n,0)); while(!q.empty()) { node now = q.front(); q.pop(); if(now.x==k) return now.step; if(!vis[now.x+1]) { q.push(node(now.x+1,now.step+1)); vis[now.x+1] = 1; } if(now.x>0 && !vis[now.x-1]) { q.push(node(now.x-1,now.step+1)); vis[now.x-1] = 1; } if(now.x*2<maxn && !vis[now.x*2]) { q.push(node(now.x*2,now.step+1)); vis[now.x*2] = 1; } } return -1;}int main(){ while(~scanf("%d %d",&n,&k)) printf("%d/n",bfs()); return 0;}

上一篇：webAPI 自动生成帮助文档

下一篇：MLlib中的数据类型