POJ 3278-Catch That Cow

POJ 3278-Catch That Cow Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 48323 Accepted: 15139 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 4 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. Source USACO 2007 Open Silver


又是一题广度搜索题,经过了上一题的锻炼,基本摸清了做广度优先搜索的套路,而且这一题比上一题还更简单一些。上一题是在三维空间里,而这一题只在一维直线上,只有三种情况:x-1、x+1、2*x。所以可以很快的写出代码: [cpp] #include<iostream> #include<queue> using namespace std; int n,k; int ans; int visited[100002]; const int MAX_DISTANCE=100000;//最大点位置 typedef struct P { int x;//坐标 int curr_min;//从n点到该点走过的时间 }; //广度优先搜索 void bfs() { queue<P> Q_P; P p,next_p; p.x=n; p.curr_min=0; visited[n]=1; Q_P.push(p); while(!Q_P.empty()) { p=Q_P.front(); Q_P.pop(); if(p.x==k) { ans=p.curr_min; return; } if(p.x-1>=0&&visited[p.x-1]==0) { visited[p.x-1]=1; next_p.x=p.x-1; next_p.curr_min=p.curr_min+1; Q_P.push(next_p); } if(p.x+1<=MAX_DISTANCE&&visited[p.x+1]==0) { visited[p.x+1]=1; next_p.x=p.x+1; next_p.curr_min=p.curr_min+1; Q_P.push(next_p); } if(2*p.x<=MAX_DISTANCE&&visited[2*p.x]==0) { visited[2*p.x]=1; next_p.x=2*p.x; next_p.curr_min=p.curr_min+1; Q_P.push(next_p); } } } int main() { cin>>n>>k; bfs(); cout<<ans; return 0; } [/cpp] 本代码提交AC,用时141MS,内存1304K。 仔细琢磨一下做过的深度搜索广度搜索的题,你会发现,一般要求最短距离、最优化问题的,都是用广度优先搜索BFS,比如这一题和上一题;如果只是求某一个可行方案,那么可以用深度搜索,比如POJ Problem 1321: 棋盘问题POJ Problem 1011: Sticks。当然广度搜索题其实也可以用深度搜索题解决,比如用深度搜索找出所有可行解,再求其中的最优解,但是这样的效率明显比只用广度搜索低。]]>

1 thought on “POJ 3278-Catch That Cow

  1. Pingback: POJ 2676-Sudoku | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *