【HDU - 2717】【POJ - 3278】Catch That Cow （经典bfs，类似dp）

71 阅读 0 评论 47 点赞

我是靠谱客的博主精明夕阳，最近开发中收集的这篇文章主要介绍【HDU - 2717】【POJ - 3278】Catch That Cow （经典bfs，类似dp），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题干：

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.

解题报告

这题用bfs去递推（其实也相当于dp啦，可以理解成只是不是按照for循环遍历的顺序去dp而已）

AC代码：

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
bool vis[300000 + 5];
int n,k;
struct Node {
	int pos,step;
	Node(){}
	Node(int pos,int step):pos(pos),step(step){}
};
int bfs(int x) {
	queue<Node> q;
	memset(vis,0,sizeof vis);
	q.push(Node(x,0));
	vis[x]=1;
	while(!q.empty()) {
		Node cur = q.front();q.pop();
		if(cur.pos == k) return cur.step;
		if( cur.pos+1<= 300000 && cur.pos+1 >= 0&&!vis[cur.pos+1] ){
			vis[cur.pos+1]=1;q.push(Node(cur.pos+1,cur.step+1));
		}
		if(cur.pos-1<= 300000&& cur.pos-1  >= 0 &&!vis[cur.pos-1]  ) {
			vis[cur.pos-1]=1;q.push(Node(cur.pos-1,cur.step+1));
		}
		if((cur.pos<<1) <= 300000 && (cur.pos<<1) >=0 &&!vis[cur.pos<<1]  ) {
			vis[cur.pos<<1]=1 ;
			q.push(Node(cur.pos<<1,cur.step+1)); 	
		}
	}
	return 0;
}
int main()
{
	
	while(~scanf("%d%d",&n,&k)) {
		printf("%dn",bfs(n));
	}
	return 0;
}

错误代码：（dp）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
ll dp[3000000 +5];
inline ll min3(ll i,ll j,ll k) {
	if(i < j) {
		return i < k ? i : k;
	}
	if(j < k) return j;
	else return k;
}
int main()
{
	int n,k;
	while(~scanf("%d%d",&n,&k)) {
		memset(dp,INF,sizeof dp);
		for(int i = 1; i<=n; i++) {
			dp[i] = min(dp[i],(ll)n-(ll)i);
			dp[i*2] = min(dp[i*2],dp[i]+1);
		}
		if(k <= n) {
			printf("%lldn",dp[k]);continue;
		}
		for(int i = n+1; i<=(k<<1); i++) {
			dp[i] = min3(dp[i],dp[i-1]+ 1,dp[i+1] + 1) ;
			dp[i*2] = min(dp[i*2],dp[i]+1);
		}
		printf("%lldn",dp[k]);
	}
	
	
	return 0;
}

总结：

这题有个很大的坑啊！！我刚开始不管数组开多大都是re，后来发现，，，数组不需要开多大，因为他有可能是负数！！所以需要判断是否越界。

其二，开30W的数组就够了，不需要300W，但是有一点要注意，判断条件中，必须判断范围在前，判断vis数组在后。

即，判断越界在前，判断其他在后。这一点非常重要！我立马想到了一般我写地图类dfs中的tx，ty也没大注意先判断越界还是先判断maze是否满足还是先判断vis是否标记过，这是因为！！！我的地图都是从1开始读入的，所以就算是先判断别的在判断txty是否越界，也不会出现re的情况，这一点是我今天才注意到的、、惭愧惭愧、、、if中判断顺序有的时候也是有区别的！！！有可能会导致越界！！