BFS —— POJ 3278 Catch That Cow

2024-09-05 04:08

文章标签 cow bfs poj catch 3278

本文主要是介绍BFS —— POJ 3278 Catch That Cow，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对应POJ题目：点击打开链接

Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 54686		Accepted: 17096

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

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

Hint

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

题意：

给出两个数n, k, (0 <= n, k <= 100000)，其中n一次可以自增1 或自减1 或乘以2，问最少经过几步可以使n = k。

思路：

分三个方向广搜，用vis数组标记以减少搜索量，注意最值边界！

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#define M 500005
#include <iostream>
using namespace std;
bool vis[M];typedef struct
{int x, s;
}Point;queue<Point>que;int bfs(int n, int k)
{Point p, p1;p.x = n, p.s = 0;que.push(p);vis[n] = 1;int i;while(!que.empty()){p = que.front();if(p.x == k) return p.s;que.pop();for(i = 0; i < 3; i++){if(0 == i) p1.x = p.x + 1;else if(1 == i) p1.x = p.x - 1;else p1.x = p.x * 2;if(p1.x < 0 || p1.x > M || vis[p1.x]) continue;vis[p1.x] = 1;p1.s = p.s + 1;que.push(p1);}}return 0;
}int main()
{//freopen("in.txt", "r", stdin);int n, k;scanf("%d%d", &n, &k);memset(vis, 0, sizeof(vis));printf("%d\n", bfs(n, k));return 0;
}

这篇关于BFS —— POJ 3278 Catch That Cow的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！