poj 3278 Catch That Cow 【BFS】

题意：从一个点n到达另外一个点m， 移动的方式有三种，*2，+1， -1。求最少到达的步数。

策略：如题。

wa了好几次。。。

只输入一组数据，用队列的时候最好吧队列声明放在函数外面否则用g++递交有可能wa（亲身体验）。但是用c++可以过的。

代码1（队列声明放在函数的外面，用c++和g++都可以a）：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;;
int n, m, ans;
bool vis[100005];
struct node{
	int cur, step;
}st;	
queue<node> q;//放在了函数的外面。
int BFS(int cur)
{
	st.cur = cur;
	st.step = 0;
	q.push(st);
	vis[st.cur] = 1;
	int i, j;
	while(!q.empty()){
		node v = q.front();
		if(v.cur == m){
			return v.step;
		}
		for(i = 0; i < 3; i ++){
			node u;
			if(i == 0){
				u.cur = v.cur*2;
				u.step = v.step+1;
			}
			if(i == 1){
				u.cur = v.cur+1;
				u.step = v.step+1;
			}
			if(i == 2){
				u.cur = v.cur-1;
				u.step = v.step+1;
			}
			if(u.cur > 100001||u.cur < 0) continue;
			if(u.cur == m){
				return u.step;
			}
			if(!vis[u.cur]){
				vis[u.cur] = 1;
				q.push(u);
			}
		}
		q.pop();
	}
}
int main()
{
	scanf("%d%d", &n, &m);
		ans = BFS(n);
		printf("%d\n" ,ans);
} 

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;;
int n, m, ans;
bool vis[100005];
struct node{
	int cur, step;
}st;	

int BFS(int cur)
{
	queue<node> q;//放在了里面
	st.cur = cur;
	st.step = 0;
	q.push(st);
	vis[st.cur] = 1;
	int i, j;
	while(!q.empty()){
		node v = q.front();
		if(v.cur == m){
			return v.step;
		}
		for(i = 0; i < 3; i ++){
			node u;
			if(i == 0){
				u.cur = v.cur*2;
				u.step = v.step+1;
			}
			if(i == 1){
				u.cur = v.cur+1;
				u.step = v.step+1;
			}
			if(i == 2){
				u.cur = v.cur-1;
				u.step = v.step+1;
			}
			if(u.cur > 100001||u.cur < 0) continue;
			if(u.cur == m){
				return u.step;
			}
			if(!vis[u.cur]){
				vis[u.cur] = 1;
				q.push(u);
			}
		}
		q.pop();
	}
}
int main()
{
	scanf("%d%d", &n, &m);
		ans = BFS(n);
		printf("%d\n" ,ans);
} 

poj 3278 Catch That Cow 【BFS】,布布扣,bubuko.com

poj 3278 Catch That Cow 【BFS】

原文：http://blog.csdn.net/shengweisong/article/details/38581725