有一个整数 A=2021,每一次,可以将这个数加 1 、减 1 或除以 2,其中除以 2 必须在数是偶数的时候才允许。
例如,2021 经过一次操作可以变成 2020、2022。
再如,2022 经过一次操作可以变成 2021、2023 或 1011。
请问,2021 最少经过多少次操作可以变成 1。
#include <bits/stdc++.h>
using namespace std;
int dist[2500];
void bfs(){
queue<int> q;
q.push(2021);
memset(dist, -1, sizeof dist);
dist[2021] = 0;
while(q.size()) {
int t = q.front();
q.pop();
if(t == 1) {
cout << dist[t];
return;
}
if(dist[t - 1] == -1) {
dist[t - 1] = dist[t] + 1;
q.push(t - 1);
}
if(dist[t + 1] == -1) {
dist[t + 1] = dist[t] + 1;
q.push(t + 1);
}
if(t % 2 == 0){
if(dist[t / 2] == -1) {
dist[t / 2] = dist[t] + 1;
q.push(t / 2);
}
}
}
}
int main(){
bfs();
return 0;
}