Catch That Cow
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 46715 | Accepted: 14673 |
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.
開始看到这道题认为和曾经做的一道题非常像，那道题直接用暴力做，一直推断能否够整除2即可了，然后一開始也想用暴力去做，可是后来做的有些情况就考虑不到，这个题目也比那个题目复制http://blog.csdn.net/whjkm/article/details/26985421
（曾经那道题目的链接），后来细致看了一下题，跟那道题还是有比較大的区别，那个题目简单就在于，它的起点是从0開始的，不能往后退；这个题目就有三种情况，向前进1，向后减1，使用传送向前进2倍的距离。開始也想不到要用bfs，看到了这个题目的分类是bfs，然后採用bfs来做。
（曾经那道题目的链接），后来细致看了一下题，跟那道题还是有比較大的区别，那个题目简单就在于，它的起点是从0開始的，不能往后退；这个题目就有三种情况，向前进1，向后减1，使用传送向前进2倍的距离。開始也想不到要用bfs，看到了这个题目的分类是bfs，然后採用bfs来做。
这个题目的基本的思路就是 3 入口的bfs，先把第一个点的3种情况入队，标记这个点已经訪问，再把下一个位置的3种情况入队，这里也有剪枝，（剪枝參考别人的）效率提高了不少，直到找到终于的那个点。
以下是代码，用数组模拟队列；
#include <cstdio>
#include <cstring>
const int maxn=200030;
typedef struct Queue //一个结构体，保存这个点的位置，和到这个点所用的时间
{
int count,step;
}Queue;
Queue queue[maxn];//队列数组
int visit[maxn];//訪问数组
void bfs(int n,int k)
{
int front=0,rear=0;
queue[rear].step=n;//把初始位置入队
queue[rear++].count=0;
visit[n]=1;//标记訪问
while(front<rear)
{
Queue q=queue[front++];
if(q.step==k)//找到终点位置
{
printf("%d\n",q.count);
break;
}
if(q.step-1>=0 && !visit[q.step-1])//注意剪枝的条件，一定要注意能够等于0
{
visit[q.step]=1;
queue[rear].step=q.step-1;//向后寻找一位
queue[rear++].count=q.count+1;//时间+1
}
if(q.step<=k && !visit[q.step+1])//剪枝
{
visit[q.step+1]=1;
queue[rear].step=q.step+1;//向前寻找一位
queue[rear++].count=q.count+1;
}
if(q.step<=k && !visit[q.step*2])//剪枝
{
visit[q.step*2]=1;//传送的情况
queue[rear].step=q.step*2;
queue[rear++].count=q.count+1;
}
}
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(visit,0,sizeof(visit));
bfs(n,k);
}
return 0;
}
也能够用STL写，效率就没有自己手动写的高，还有标记数组用bool比較节省内存；
我自己用STL又写了一次，思路和上面的一样；
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=200030;
queue<int>q;
int Count[maxn];
bool visit[maxn];
void bfs(int n,int k)
{
q.push(n);
visit[n]=1;
Count[n]=0;
while(!q.empty())
{
int x=q.front();
q.pop();
if(x==k)
{
printf("%d\n",Count[x]);
break;
}
if(x-1>=0 && !visit[x-1])
{
q.push(x-1);
visit[x-1]=1;
Count[x-1]=Count[x]+1;
}
if(x<=k && !visit[x+1])
{
q.push(x+1);
visit[x+1]=1;
Count[x+1]=Count[x]+1;
}
if(x<=k && !visit[2*x])
{
q.push(x*2);
visit[x*2]=1;
Count[x*2]=Count[x]+1;
}
}
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(visit,0,sizeof(visit));
bfs(n,k);
}
return 0;
}
看到别人的一种写法，貌似也不错，分三个方向进行搜索
#include <iostream>
#include <queue>
#define SIZE 100001 using namespace std; queue<int> x;
bool visited[SIZE];
int step[SIZE]; int bfs(int n, int k)
{
int head, next;
//起始节点入队
x.push(n);
//标记n已訪问
visited[n] = true;
//起始步数为0
step[n] = 0;
//队列非空时
while (!x.empty())
{
//取出队头
head = x.front();
//弹出队头
x.pop();
//3个方向搜索
for (int i = 0; i < 3; i++)
{
if (i == 0) next = head - 1;
else if (i == 1) next = head + 1;
else next = head * 2;
//越界就不考虑了
if (next > SIZE || next < 0) continue;
//判重
if (!visited[next])
{
//节点入队
x.push(next);
//步数+1
step[next] = step[head] + 1;
//标记节点已訪问
visited[next] = true;
}
//找到退出
if (next == k) return step[next];
}
}
} int main()
{
int n, k;
cin >> n >> k;
if (n >= k)
{
cout << n - k << endl;
}
else
{
cout << bfs(n, k) << endl;
}
return 0;
}