結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-10-29 21:47:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 827 bytes |
コンパイル時間 | 1,645 ms |
コンパイル使用メモリ | 171,940 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 09:09:56 |
合計ジャッジ時間 | 2,612 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
#include "bits/stdc++.h" using namespace std; int main() { int N, len=14; cin >> N; bool flag[11111] = { false }; struct PAIR { int first, second; // first:マス目, second:手数(深さ) }; queue<PAIR> que; que.push(PAIR{ 1,1 }); while (!que.empty()) { PAIR n = que.front(); que.pop(); if (flag[n.first] == true) continue; flag[n.first] = true; if (n.first == N) { cout << n.second << endl; return 0; } if (n.second > N) { cout << -1 << endl; return 0; } if(n.first > N) continue; int cnt=0; for (int bit = 0; bit < len; bit++) { if(n.first & (1<<bit)) cnt++; } //cout << n.first << " " << n.second; //cout <<" "<< cnt << endl; que.push(PAIR{ n.first - cnt,n.second + 1 }); que.push(PAIR{ n.first + cnt,n.second + 1 }); } if(!flag[N]) cout << -1 << endl; }