BFS专攻：POJ 3278 （三个方向的简单BFS）

83 阅读 0 评论 55 点赞

我是靠谱客的博主超帅美女，这篇文章主要介绍BFS专攻：POJ 3278 （三个方向的简单BFS），现在分享给大家，希望可以做个参考。

题意不用说了，那么短……

因为每一步有三种可能，-1，+1或者*2,所以把这三个方向都加入队列就行了……-1的时候>=0,+1和*2的时候得<=100000，刚开始写的<=k然后WA了一发，才发现是这个原因错了，因为样例中18的时候就比17小了，所以……还有就是标记一下哪个数已经判断过了，判断的就不用再判断了……

复制代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int n,k,map[100005];   //因为全局变量是存放有堆中，而堆中是已经默认初始化为0了，而且这里只用输入一个样例，下面就不用初始化为0了
struct abc
{
    int t,x;
};
queue<abc>q;
int bfs()
{
    abc p;
    p.x=n;
    p.t=0;
    q.push(p);
    while(!q.empty())
    {
        abc ans,tem;
        ans=q.front();
        q.pop();
        if(ans.x-1>=0&&!map[ans.x-1])
        {
            tem.x=ans.x-1;
            tem.t=ans.t+1;
            q.push(tem);
            map[tem.x]=1;
        }
        if(tem.x==k) return tem.t;   //每个方向都要判断一下，因为可能已经等于K了

if(ans.x+1<=100000&&!map[ans.x+1])
        {
            tem.x=ans.x+1;
            tem.t=ans.t+1;
            q.push(tem);
            map[tem.x]=1;
        }
        if(tem.x==k) return tem.t;

if(ans.x*2<=100000&&!map[ans.x*2])
        {
            tem.x=ans.x*2;
            tem.t=ans.t+1;
            q.push(tem);
            map[tem.x]=1;
        }
        if(tem.x==k) return tem.t;
    }
}
int main()
{
    cin>>n>>k;
    if(n==k) printf("0n");
    else printf("%dn",bfs());
    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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int n,k,map[100005];   //因为全局变量是存放有堆中，而堆中是已经默认初始化为0了，而且这里只用输入一个样例，下面就不用初始化为0了
struct abc
{
    int t,x;
};
queue<abc>q;
int bfs()
{
    abc p;
    p.x=n;
    p.t=0;
    q.push(p);
    while(!q.empty())
    {
        abc ans,tem;
        ans=q.front();
        q.pop();
        if(ans.x-1>=0&&!map[ans.x-1])
        {
            tem.x=ans.x-1;
            tem.t=ans.t+1;
            q.push(tem);
            map[tem.x]=1;
        }
        if(tem.x==k) return tem.t;   //每个方向都要判断一下，因为可能已经等于K了

        if(ans.x+1<=100000&&!map[ans.x+1])
        {
            tem.x=ans.x+1;
            tem.t=ans.t+1;
            q.push(tem);
            map[tem.x]=1;
        }
        if(tem.x==k) return tem.t;

        if(ans.x*2<=100000&&!map[ans.x*2])
        {
            tem.x=ans.x*2;
            tem.t=ans.t+1;
            q.push(tem);
            map[tem.x]=1;
        }
        if(tem.x==k) return tem.t;
    }
}
int main()
{
    cin>>n>>k;
    if(n==k) printf("0n");
    else printf("%dn",bfs());
    return 0;
}