`
人生难得糊涂
  • 浏览: 113851 次
社区版块
存档分类
最新评论

poj3278-分支限界法

 
阅读更多

题目大意:一个农夫抓牛,农夫坐标为n,牛坐标为p,农夫有三种移动方式,1.从x到x-1 .2.从x到x+1 3.从x到2*x;   求农夫抓到牛所需移动最少的步数。

 思路:做题的时候知道是属于分支限界法这类的题,于是采用BFS ,如果事先不知道的话 可能会用DFS递归搜索。。   重点是在剪枝上,要注意两个方面的剪枝,1是当前节点的值如果大于牛的坐标的话 ,那 x+1 x*2 的移动方式就不入队列(即剪枝)。2是记录走过的节点,走过的节点不再走(这个我很惭愧的没想到,一直TLE后老师说了以后再AC的)。

具体看代码

#include<iostream>
#include<queue>
using namespace std;
int vis[200010];//标记数组 记录走过的元素
int main()
{
	int n,k;
	
	queue<int>q;
	scanf("%d",&n);
	scanf("%d",&k);
	if(n==k)
	{
		cout<<0<<endl;
		return 0;
	}
	q.push(n);
	vis[n]=1;
	q.push(-1);
	int flag=0;
	
	int step=0;
	while(true)
	{
		int t,t1,t2,t3,t4;
		t=q.front();
		q.pop();
		if(t==-1)
		{
			q.push(-1);
			step++;
			continue;
		}
		
		t1=t*2;
		t2=t+1;
		t3=t-1;
		t4=-1;
		
		if(t1==k||t2==k||t3==k)
		{
			step++;
			cout<<step<<endl;
			break;
		}
		if(t1<0||t1>100000||t>k||vis[t1]==1)
			;
		else
			q.push(t1);

		if(t2<0||t2>100000||t>k||vis[t2]==1)
			;
		else
			q.push(t2);
		if(t3<0||t3>100000||vis[t3]==1)
			;
		else
			q.push(t3);
		vis[t1]=1;
		vis[t2]=1;
		vis[t3]=1;
		
	}
	return 0;
}

 

0
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics