結果

問題 No.3 ビットすごろく
コンテスト
ユーザー tomoyaatcoder
提出日時 2019-10-05 19:43:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
実行時間 -
コード長 1,571 bytes
コンパイル時間 1,450 ms
コンパイル使用メモリ 165,468 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-06 22:18:24
合計ジャッジ時間 6,469 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 RE * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(std::vector<int>&, int&, int&, std::vector<bool>&)’:
main.cpp:51:1: warning: control reaches end of non-void function [-Wreturn-type]
   51 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>
#include <stack>
using namespace std;

int binary_convert(int i){
  if(i <= 1){
    return i;
  }
  int ret = 0;
  vector<int> a;
  while(i >= 2){
    a.insert(a.begin(), i % 2);
    i /= 2;
  }
  a.insert(a.begin(), i);
  for(int i = 0; i < a.size(); i++){
    ret += a.at(i) * pow(10, a.size() - i - 1);
  }
  return ret;
}

vector<bool> visited;

// たどり着くとそこまでにかかった回数、たどり着けなければ-1を返す
int dfs(vector<int> &boxes, int &current_index, int &ans, vector<bool> &visited){
  visited.at(current_index) = true;
  bool impossible = true;
  if(boxes.size() == 1){
    return 0;
  }
  for(int i = 0; i < visited.size(); i++){
    if(visited.at(i) == false){
      impossible = false;
      break;
    }
  }
  if(impossible){
    return -1;
  }
  if(current_index == boxes.size() - 1){
    return ans;
  }
  if(current_index > boxes.size() - 1 || current_index < 0){
    return -1;
  }
  for(int i = -1; i <= 1; i += 2){
    current_index += boxes.at(current_index) * i;
    ans++;
    dfs(boxes, current_index, ans, visited);
  }
}

int main() {
  int N;
  cin >> N;
  vector<int> boxes(N);
  for(int i = 0; i < N; i++){
    int a = binary_convert(i + 1);
    string a_str = to_string(a);
    int b = 0;
    for(int i = 0; i < a_str.size(); i++){
      if(a_str[i] == '1'){
        b++;
      }
    }
    boxes.at(i) = b;
  }
  int current_index = 0;
  int ans = 1;
  vector<bool> visited(N, false);
  visited.at(0) = true;
  cout << dfs(boxes, current_index, ans, visited) << endl;
  return 0;
}
0