搜索小练#6

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Prime Path 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 10000+10;
const int INF = 21474836;

int t, res, cnt;

int dp[N], v[N], prime[N];

inline int work (int num, int t, int c) {
    if (t == 0) return num/10*10+c;
    if (t == 1) return num/100*100+c*10+num%10;
    if (t == 2) return num/1000*1000+c*100+num%100;
    return c*1000+num%1000;
}

int main () {
    memset (v, 1, sizeof v);
    for (int i = 2; i <= N; ++ i) {
        if (v[i]) prime[++cnt] = i;
            for (int j = 1; j<=cnt && i*prime[j]<=N; ++ j) 
                v[i*prime[j]] = 0;
    }
    cin >> t;
    while (t --> 0) {
        int a, b;
        cin >> a >> b;
        if (a == b) {puts("0");continue;}
        memset (dp, INF, sizeof dp);
        dp[a] = 0;
        queue<int>q;
        q.push(a);
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int i = 0; i < 4; ++ i)
                for (int j = 0; j < 10; ++ j) {
                    if (i == 3 && j == 0) continue;
                    int nxt = work (cur, i, j);
                    if (!v[nxt] || dp[nxt] <= dp[cur]) continue;
                    dp[nxt] = dp[cur]+1;
                    q.push(nxt);
                }
        }
        cout << dp[b] << '\n';
    }
}

PS:

1.easy \(bfs\)

2.but is not very easy to find a thought

3.I felt that I have thought vaguely but I can'nt make it.

I will still work hard!

两年后，再一次做这道题，思路清晰但是代码能力下降好多，debug了好长时间

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
/*
 * By Youngore
 * Time: 22.10.15
 * */
#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#define inf 10000
const int N = 1e4 + 66;
using namespace std;

int T, cnt, a[66];
int vis[N], pri[N], v[N];

inline void pre()
{
	memset(vis, 1, sizeof vis); vis[1] = 0;
	int i, j;
	for (i = 2; i <= inf; ++ i)
	{
		if (vis[i]) pri[++ cnt] = i;
		for (j = 1; j <= cnt && i * pri[j] <= inf; ++ j)
		{
			vis[i * pri[j]] = 0;
			if (! (i % pri[j])) break;
		}
	}
	return;
}

inline int youngore()
{
	scanf ("%d", &T); pre();
	while (T --> 0)
	{
		int x, y, i, j;
		scanf ("%d%d", &x, &y);
		memset(v, 0, sizeof v);
		queue<pair<int,int> >q; q.push(make_pair(x,0));
		v[x] = 1;
		while (! q.empty())
		{
			pair<int, int> nows = q.front(); q.pop();
			if (nows.first == y)
			{
				cout << nows.second << '\n';
				break;
			}
			int k = nows.first, cnt = 0;
			while (k)
			{
				a[++ cnt] = k % 10;
				k /= 10;
			}
			for (k = cnt; k >= 1; -- k)//枚举每一位
			{
				for (i = ((k == cnt) ? 1 : 0); i <= 9; ++ i)//枚举该位可以替换成那些数字
				{
					if (i == a[k]) //如果碰到了原位上的数字
						continue;
					int res = 0;
					for (j = cnt; j >= 1; -- j)//把每一位加和
						res = res * 10 + ((j == k) ? i : a[j]);
					if (vis[res] && !v[res]) q.push(make_pair(res, nows.second + 1)), v[res] = 1;
				}
			}
		}
	}
	return 0;
}

int search_ex = youngore();

signed main() {;}
/*
1
1033 8179
*/