kuangbin 简单搜索 - POJ - 3278 Catch That Cow （简单bfs）

3.kuangbin 简单搜索 - POJ - 3278 Catch That Cow （简单bfs）

简单bfs

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
//#define int ll
#define INF 0x3f3f3f3f
using namespace std;
int read()
{
	int w = 1, s = 0;
	char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0';    ch = getchar(); }
	return s * w;
//最大公约数
}int gcd(int x,int y) {
    if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后
    //递归终止条件千万不要漏了，辗转相除法
    return x % y ? gcd(y, x % y) : y;
}
int lcm(int x,int y)//计算x和y的最小公倍数
{
    return x * y / gcd(x, y);//使用公式
}
//------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
const int N = 100010;
bool vis[N];
int Map[N];
int start, dis;
queue<int> Q;
int n, k;
int bfs()
{
    Q.push(n);//入队
    while (!Q.empty()) {
        start = Q.front();
        Q.pop();
        for(int i = 0; i < 3; ++i) {
            if (i == 0) //后退一步
                dis = start - 1;
            else if (i == 1) //前进一步
                dis = start + 1;
            else//瞬移两倍
                dis = start + start;
            if (dis < 0 || dis > 100000)
                continue;
            if (!vis[dis]) {
                Q.push(dis);
                Map[dis] = Map[start] + 1;
                vis[dis] = true;
            }
            if (dis == k) {
                return Map[dis];    
            }
        }
    }
}
int main()
{
    cin >> n >> k;
    if (n >= k) {
        printf("%d\n", n - k);
    } else {
        printf("%d\n", bfs());
    }
    return 0;
}

本文地址：https://blog.csdn.net/m0_46272108/article/details/108840290