結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2014-11-17 18:11:37 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 809 bytes |
コンパイル時間 | 613 ms |
コンパイル使用メモリ | 72,056 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 07:07:07 |
合計ジャッジ時間 | 1,605 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include <iostream> #include <queue> #include <map> #include <algorithm> #define INF (2 << 28) using namespace std; int bfs(int n){ int used[11111]; fill_n(used, 11111, INF); queue <pair<int, int> > que; que.push(make_pair(1, 0)); while(!que.empty()){ int now = que.front().first, cnt = que.front().second; que.pop(); if(now == n) return cnt + 1; int inc = __builtin_popcount(now); if(now + inc <= n && used[now + inc] > cnt + 1){ que.push(make_pair(now + inc, cnt + 1)); used[now + inc] = cnt + 1; } if(now - inc > 0 && used[now - inc] > cnt + 1){ que.push(make_pair(now - inc, cnt + 1)); used[now - inc] = cnt + 1; } } return -1; } int main(){ int n; cin >> n; cout << bfs(n) << endl; }