题目描述:
http://acm.hdu.edu.cn/showproblem.php?pid=2717
中文大意:
农夫要抓牛,初始时,农夫的坐标为 N ,牛的坐标为 K。
农夫可以选择步行或传送。
若农夫当前位于 X 处,则一分钟内可以步行到 X + 1 或 X - 1 两个位置,可以传送到 2 * X 位置处。
要求:计算农夫抓到牛的最短用时。
思路:
队列节点记录的是农夫当前位置和所耗时间。
弹出队列首节点,确定了农夫的当前位置信息后,农夫下一步有三种走法:前进、后退、传送。
而下一步到达的位置 next.pos 应该限制在 [0,100000] 范围内,不然会超出数据范围。
代码:
#include<bits/stdc++.h>
using namespace std;
struct node{
int pos,time;
};
int n,k;
bool visited[100001];
int bfs(){
node start,next;
start.pos = n;
start.time = 0;
visited[n] = true;
queue<node> q;
q.push(start);
while(!q.empty()){
start = q.front();
q.pop();
if(start.pos == k){
return start.time;
}
for(int i=0;i<3;i++){
switch(i){
case 0:
next.pos = start.pos + 1;
break;
case 1:
next.pos = start.pos - 1;
break;
case 2:
next.pos = start.pos * 2;
break;
}
//注意对范围做限制
if(next.pos>=0 && next.pos<=100000 && !visited[next.pos]){
visited[next.pos] = true;
next.time = start.time + 1;
q.push(next);
}
}
}
}
int main(){
while(~scanf("%d %d", &n, &k)){
memset(visited, false, sizeof(visited));
printf("%d
", bfs());
}
}