yukicoder 0003 ビットすごろく
問題文概要
$1, \dots, N$ が書いてあるマスが, 順に, 直線上にならんでいる. この上ですごろく的なことをする. マス $i$ では, $i$ を $2$ 進表記した時の $1$ の数ちょうど, 進むか戻ることが出来る. 但し, 盤外に移動する事は出来ない.
何回の移動で $1$ から $N$ まで行けるだろうか.
制約
$1 \le N \le 10^4$.
解法
bfs する.
ソースコード
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool solve(){
int n;
cin >> n;
vector<int> d(n+1, bit(30));
queue<int> q;
q.emplace(1); d[1] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
int t = __builtin_popcount(u);
if(u-t > 0) if(chmin(d[u-t], d[u]+1)) q.emplace(u-t);
if(u+t <= n) if(chmin(d[u+t], d[u]+1)) q.emplace(u+t);
}
if(d[n] == bit(30)) d[n] = -1;
cout << d[n] << endl;
return true;
}