P1588 丢失的牛
- 158通过
- 654提交
- 题目提供者JOHNKRAM
- 标签USACO
- 难度普及/提高-
- 时空限制1s / 128MB
提交 讨论 题解
最新讨论更多讨论
- 答案下载下来是对的，但过不…
- 此题卡stl的queue？
- 假的编译器。。。
- 怎么A不了
题目描述
FJ丢失了他的一头牛，他决定追回他的牛。已知FJ和牛在一条直线上，初始位置分别为x和y，假定牛在原地不动。FJ的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到2*x的位置。计算他至少需要几步追上他的牛。
输入输出格式
输入格式：
第一行为一个整数t(≤10)，表示数据组数；接下来每行包含一个两个正整数x和y(x,y≤10^5)，分别表示FJ和牛的坐标。
输出格式：
对于每组数据，输出最少步数。
输入输出样例
输入样例#1：
1
5 17
输出样例#1：
4
分析：这道题使我更深刻的理解了dfs和bfs的区别，直接dfs是不行的，因为一条道走到黑，而且不能确保步数最少，所以用bfs，这样每扩展一步都是步数最少的，这样的话还要加上剪枝：1.如果走到负数就不要-1了 2.如果大于y就不增加了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string> using namespace std; int t, x, y,d[]; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &x, &y);
memset(d, , sizeof(d));
queue <int> q;
q.push(x);
while (!q.empty())
{
int t = q.front();
q.pop();
if (t == y)
{
printf("%d\n", d[t]);
break;
}
if (t - > && (!d[t - ] || d[t - ] > d[t] + ))
{
d[t - ] = d[t] + ;
q.push(t - );
}
if (t >= y)
continue;
if ( * t < && (!d[*t] || d[*t] > d[t] + ))
{
d[*t] = d[t] + ;
q.push(*t);
}
if (t + < && (!d[t + ] || d[t + ] > d[t] + ))
{
d[t + ] = d[t] + ;
q.push(t + );
}
}
} return ;
}