搜索小练#3

Posted on Edited on In

题目

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
// catch that cow
#include <iostream>
using namespace std;

const int N = 1e7+10;

int n, k, x;
int q[N], v[N], dis[N];

int main () {
    cin >> n >> k;
    if (n > k) {cout << n-k; return 0;}
    int s = 0, t = 1;
    q[1] = n, v[n] = 1;
    while (s <= t) {
        ++ s;
        for (int i = 1; i <= 3; ++ i) {
            int x = q[s];
            if (i == 1) ++ x; 
            if (i == 2) -- x;
            if (i == 3) x<<=1;
            if (x >= 0 && x <= 100000) 
                if (!v[x]) {
                    v[x] = 1;
                    q[++ t] = x;
                    dis[x] = dis[q[s]] + 1;
                }
        }
    }
    cout << dis[k];
    return 0;
}

PS:

1.before today I break for two days;

2.It is a very easy bfs.

The only season why I cann't solve this problem is I was very sily

第二次做，考虑一下正确性

1
s.cnt = now.cnt + 1;
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int n, k;
int vis[100066];
struct yhy{int w, cnt;};
queue<yhy>q;

inline int youngore()
{
	scanf ("%d%d", &n, &k);
	yhy now; now.w = n, now.cnt = 0;
	q.push(now);
	while (q.size())
	{
		now = q.front(); q.pop();
		if (now.w == k)
		{
			cout << now.cnt;
			return 0;
		}
		yhy s;
		for (int i = 1; i <= 3; ++ i)
		{
			if (i == 1) s.w = now.w + 1;
			if (i == 2) s.w = now.w - 1;
			if (i == 3) s.w = now.w * 2;
			if (s.w < 0 || s.w > 100000)
			{
				continue;
			}
			if (! vis[s.w])
			{
				vis[s.w] = 1;
				s.cnt = now.cnt + 1;
				q.push(s);
			}
		}
		//cout << "!!!----> " << q.size() << '\n';
	}
	return 0;
}

signed main(){youngore();}
/*
*/