結果

問題 No.3 ビットすごろく
ユーザー tomoyaatcodertomoyaatcoder
提出日時 2019-10-05 19:43:46
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,571 bytes
コンパイル時間 1,521 ms
コンパイル使用メモリ 165,728 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-16 07:42:19
合計ジャッジ時間 6,707 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 WA -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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