题目大意:一个农夫抓牛,农夫坐标为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; }
相关推荐
北大POJ3278-Catch That Cow 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
POJ1724-ROADS 测试数据。数据来源:CEOI 1998 Round II
POJ1523 - SPF 测试数据。 数据来源:Greater New York 2000 问题H
POJ1472-Instant Complexity 测试数据。数据来源:Southwestern European Regional Contest 1997
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
经典的状态DP难题,非常好的的题目,我做了很久才做出来,强烈推荐!!1
北大POJ2002-Squares 解题报告+AC代码
北大ACM-POJ1010 - STAMPS 原比赛(Pacific Northwest 1998)题目的测试数据
ACM-POJ2115-C Looooops 测试数据。 数据来源:CTU Open 2004 问题C