蚂蚁笔试
给定一个x和p,有两种操作,每次可以给x+1或者将p中的两个位数交换,求将x转换成p的倍数的最小操作数
分析: 假如x是p的倍数,操作数就是0,然后一次操作可以达到加一或者位数交换的所有情况,依次类推,形成一个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
| #include<bits/stdc++.h>
using namespace std;
int x,p;
map<int,int>mp;
void bfs()
{
queue<int>q;
q.push(x);
mp[x] = 0;
while(!q.empty())
{
int nw = q.front();
q.pop();
q.push(nw+1);
mp[nw+1] = mp[nw] + 1;
if((nw+1)%p==0)
{
cout << mp[nw] + 1;
return;
}
string sn = to_string(nw);
for(int i = 0;i<sn.size();i++)
{
for(int j = 0;j<sn.size();j++)
{
if(i!=j)
{
char temp = sn[i];
sn[i] = sn[j];
sn[j] = temp;
int tn = stoi(sn);
if(tn % p==0)
{
cout << mp[nw] + 1;
return;
}
q.push(tn);
mp[tn] = mp[nw] + 1;
}
}
}
}
}
int main()
{
cin >> x >> p;
mp[x] = 0;
bfs();
return 0;
}
|
python代码的话更简洁一些,可以抽空多学学,还是不太熟,只是看得多,没上手实操过多少
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
| from collections import deque
def bfs(x, p):
q = deque([x])
sts = {x: 0}
while q:
nw = q.popleft()
nxt = nw + 1
if nxt not in sts:
q.append(nxt)
sts[nxt] = sts[nw] + 1
if nxt % p == 0:
return sts[nxt]
snw = str(nw)
for i in range(len(snw)):
for j in range(len(snw)):
if i != j:
lnw = list(snw)
lnw[i], lnw[j] = lnw[j], lnw[i]
snwpt = int(''.join(lnw))
if snwpt not in sts:
q.append(snwpt)
sts[snwpt] = sts[nw] + 1
if snwpt % p == 0:
return sts[snwpt]
return -1
x, p = map(int, input().split())
print(bfs(x, p))
|