Catch That Cow OpenJ_Bailian - 4001 (BFS)

92 阅读 0 评论 61 点赞

我是靠谱客的博主安详硬币，这篇文章主要介绍Catch That Cow OpenJ_Bailian - 4001 (BFS)，现在分享给大家，希望可以做个参考。

题意: x坐标系上, 人在n点, 一头牛在k点, 人有两种走法 1. x+-1 2.x*=2, 求抓到牛的最小步数

直接一直感觉深搜和广搜没什么区别，所以就只学了深搜，觉得很多题目深搜也就够了吧。

昨天才发现有些题目的话，用深搜是会炸的，大部分都是求最优解或最短路径的问题。因为深搜需要不断地前进->回溯，而广搜一边下来有时候可能没完就已经找到答案了。

这道题目是一题基础的广搜题目，直接递推就解决了，所以我也没写递归。跟广搜的大多数题目很相似：用队列来维护出发的顶点，每一个顶点都判断是否能扩展。。。

还要说一下，之前的代码一直RE，后来发现忽略了&&短路的特性，导致下标溢出

复制代码

//Catch that cow
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

int N,K;
const int maxn = 100010;
bool visited[maxn];
struct Step{
    int x, steps; //位置和层（步）数
    Step(int xx, int s):x(xx),steps(s) { }
};
queue<Step> q;
int main()
{
    scanf("%d%d",&N,&K);
    memset(visited, 0, sizeof(visited));
    while(!q.empty()) q.pop();  //清空队列
    q.push(Step(N,0));
    visited[N] = true;
    while(!q.empty()){
        Step s = q.front(); //取出队列头结点
        if(s.x == K){ //终点
            printf("%dn",s.steps);
            return 0;
        }
        else{  //对于每一个可扩展的点层数+1
            if(s.x+1<=maxn && !visited[s.x+1]){
                q.push(Step(s.x+1, s.steps+1));
                visited[s.x+1] = true;
            }
            if(s.x-1>=0 && !visited[s.x-1]){
                q.push(Step(s.x-1, s.steps+1));
                visited[s.x-1] = true;
            }
            if(s.x*2<=maxn && !visited[s.x*2]){
                q.push(Step(s.x*2, s.steps+1));
                visited[s.x*2] = true;
            }
            q.pop(); //走过的顶点直接遗弃即可
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//Catch that cow
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

int N,K;
const int maxn = 100010;
bool visited[maxn];
struct Step{
    int x, steps; //位置和层（步）数
    Step(int xx, int s):x(xx),steps(s) { }
};
queue<Step> q;
int main()
{
    scanf("%d%d",&N,&K);
    memset(visited, 0, sizeof(visited));
    while(!q.empty()) q.pop();  //清空队列
    q.push(Step(N,0));
    visited[N] = true;
    while(!q.empty()){
        Step s = q.front(); //取出队列头结点
        if(s.x == K){ //终点
            printf("%dn",s.steps);
            return 0;
        }
        else{  //对于每一个可扩展的点层数+1
            if(s.x+1<=maxn && !visited[s.x+1]){
                q.push(Step(s.x+1, s.steps+1));
                visited[s.x+1] = true;
            }
            if(s.x-1>=0 && !visited[s.x-1]){
                q.push(Step(s.x-1, s.steps+1));
                visited[s.x-1] = true;
            }
            if(s.x*2<=maxn && !visited[s.x*2]){
                q.push(Step(s.x*2, s.steps+1));
                visited[s.x*2] = true;
            }
            q.pop(); //走过的顶点直接遗弃即可
        }
    }
    return 0;
}