【bfs】抓住那头牛

2021-09-19 10:31:17

【题目】

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：

1、从X移动到X-1或X+1，每次移动花费一分钟

2、从X移动到2*X，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

【输入】

两个整数，N和K。

【输出】

一个整数，农夫抓到牛所要花费的最小分钟数。

【输入样例】

5 17

【输出样例】

【思路】就是简单的bfs，但是我忘记了上界这事了（汗~）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<bits/stdc++.h>
#include<string>
#include<cstring>
using namespace std;
const int maxn=999999999;
const int minn=-999999999;
int d[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
/*从
X移动到X-1或X+1，每次移动花费一分钟
从X移动到2*X，每次移动花费一分钟
*/
int begin,end;
int visit[900001];
struct node {
    int x;
    int time;
};
queue<node>q;
int main() {
    cin>>begin>>end;
    q.push((node) {
        begin,0
    });
    visit[begin]=1;
    while(!q.empty()) {
        node p=q.front();
        q.pop();
        if(p.x==end) {
            cout<<p.time ;
            return 0;
        }
        if(!visit[p.x-1]&&p.x-1>0&&p.x-1<100001) {
            q.push((node) {
                p.x-1,p.time+1
            });
            visit[p.x-1]=1;
        }
        if(!visit[p.x+1]&&p.x+1>0&&p.x-1<100001) {
            q.push((node) {
                p.x+1,p.time+1
            });
            visit[p.x+1]=1;
        }
        if(!visit[p.x*2]&&p.x*2>0&&p.x-1<100001) {
            q.push((node) {
                p.x*2,p.time+1
            });
            visit[p.x*2]=1;
        }
    }
    return 0;
}

码农公寓