洛谷 P1588 丢失的牛

题目描述

FJ丢失了他的一头牛，他决定追回他的牛。已知FJ和牛在一条直线上，初始位置分别为x和y，假定牛在原地不动。FJ的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到2*x的位置。计算他至少需要几步追上他的牛。

输入输出格式

输入格式：

第一行为一个整数t(≤10)，表示数据组数；接下来每行包含一个两个正整数x和y(0<x,y≤10^5)，分别表示FJ和牛的坐标。

输出格式：

对于每组数据，输出最少步数。

输入输出样例

输入样例#1：

1

5 17

输出样例#1：

4

 

 

bfs

哎 为了省行数把俩if合并了。。

卡了40分钟。。

屠龙宝刀点击就送

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

struct node

{

    int x,tim;

};

queue<node>q;

int t,x,y;

int calc(int x,int now) {return x==?now+:(x==?now*:now-);}

int main()

{

    scanf("%d",&t);

    for(;t--;)

    {

        bool vis[];

        memset(vis,,sizeof(vis));

        scanf("%d%d",&x,&y);

        for(;!q.empty();q.pop());

        node tmp;

        tmp.x=x;

        tmp.tim=;

        vis[x]=;

        q.push(tmp);

        for(node now;!q.empty();)

        {

            now=q.front();

            q.pop();

            if(now.x==y) {printf("%d\n",now.tim);break;}

            for(int i=;i<=;++i)

            {

                int to=calc(i,now.x);

                if(to>&&to<=)

                {

                    if(!vis[to])

                    {

                        node nex;

                        vis[to]=;

                        nex.x=to;

                        nex.tim=now.tim+;

                        q.push(nex);

                    }

                }

            }

        }

    }

    return ;

}