By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：

题目大意：

同一行上有两个点，从n点到k点有两个，求从n点出发到k点要的最小操作数

  • 操作1：到x - 1处
  • 操作2：到x + 1处
  • 操作3：到2*x处

分析：

首先想到的应该是BFS，找最短路径

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//版本一：
//用了STL里的queue，会慢一点

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;

const int MAXN = 100030;

bool vis[MAXN];			//用vis数组剪枝

struct node{
    int x;              //代表该点
    int step;           //到达该点的步数
};

void BFS(int n, int k)
{
    int xx;
    queue<node> que;
    node q;
    q.x = n, q.step = 0;
    que.push(q);
    vis[n] = true;
    while(!que.empty()){
        node head = que.front();
        que.pop();
        for(int i = 0; i < 3; i++){
            if(i == 0)
                xx = head.x - 1;
            else if(i == 1)
                xx = head.x + 1;
            else
                xx = head.x * 2;

            if(xx < 0 || xx > 100000 || vis[xx])
                continue;

            node tmp;
            if(!vis[xx]){
                tmp.x = xx, tmp.step = head.step + 1;
                que.push(tmp);
                vis[xx] = true;
            }
            if(xx == k){
                printf("%d\n", tmp.step);//BFS的特性,返回的第一个一定是最短的路径
                return ;//一开始只输入了n,k都用上了，输入流里没有其他的数据了，可以直接return，输入下一组数据
            }
        }
    }
}

int main()
{
    int n, k;
    while(scanf("%d%d", &n, &k) == 2){
        memset(vis, false, sizeof(vis));
        if(n >= k)
            printf("%d\n", n - k);
        else
            BFS(n, k);
    }
    return 0;
}


//////////////////////
//版本二：
//用数组模拟队列
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;

const int MAXN = 100030;

int a[MAXN];			//a数组同时记录是否访问过且step是多少
int que[MAXN];

void BFS(int n, int k)
{
    int head, tail, x;
    head = tail = 0;
    a[n] = 0;
    que[tail++] = n;		//push
    while(head < tail){
        int h = que[head++];	//pop
        if(h == k){
            printf("%d\n", a[h]);
            return ;
        }
        x = h + 1;
        if(x <= 100000 && a[x] == -1){
            a[x] = a[h] + 1;
            que[tail++] = x;
        }
        x = h - 1;
        if(x <= 100000 && a[x] == -1){
            a[x] = a[h] + 1;
            que[tail++] = x;
        }
        x = h * 2;
        if(x <= 100000 && a[x] == -1){
            a[x] = a[h] + 1;
            que[tail++] = x;
        }
    }
}

int main()
{
    int n, k;
    while(scanf("%d%d", &n, &k) == 2){
        memset(a, -1, sizeof(a));
        memset(que, 0, sizeof(que));
        BFS(n, k);
    }
    return 0;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：