C++でゲームIIIをジャンプします

負でない整数の配列arrがあるとすると、最初は配列の開始インデックスに配置されます。インデックスiにいるときは、i +arr[i]またはi--arr[i]にジャンプして、値0のインデックスに到達できるかどうかを確認できます。外部にジャンプできないことに注意する必要があります。いつでもアレイ。したがって、入力が次のようになっている場合：arr =[4,2,3,0,3,1,2]で、5から開始すると、5→4→1→3、または5→6→のように出力が真になります。 4→1→3。

これを解決するには、次の手順に従います-

• n：=arrのサイズ
• キューqを定義し、startをqに挿入し、visitedというセットを定義し、startをvisitedセットに挿入します
• キューが空でない間、
  • curr：=qのフロント要素、qからフロント要素を削除
  • array [curr]が0の場合、trueを返します
  • curr + arr[curr]
  • curr +arr[curr]をqに挿入
  • 訪問者にcurr+arr[curr]を挿入
• curr --arr [curr]> =0であり、curr --arr [curr]が訪問済みセットに存在しない場合、
  • curr--arr[curr]をqに挿入
  • curr--arr[curr]をvisitedに挿入

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canReach(vector<int>& arr, int start) {
      int n = arr.size();
      queue <int> q;
      q.push(start);
      set <int> visited;
      visited.insert(start);
      while(!q.empty()){
         int curr = q.front();
         q.pop();
         if(arr[curr] == 0)return true;
         if(curr + arr[curr] < n && !visited.count(curr + arr[curr])){
            q.push(curr + arr[curr]);
            visited.insert(curr + arr[curr]);
         }
         if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])){
            q.push(curr - arr[curr]);
            visited.insert(curr - arr[curr]);
         }
      }
      return false;
   }
};
main(){
   vector<int> v = {4,2,3,0,3,1,2};
   Solution ob;
   cout << (ob.canReach(v, 5));
}

入力

[4,2,3,0,3,1,2]
5

出力

1