C++でゲームIVをジャンプする

arrという整数の配列があるとします。最初はインデックス0にいます。1つのステップで、インデックスiからi + xにジャンプできます。ここで、i +x =0。jここで：arr[i]とarr[j]は同じであり、iとjは同じではありません。ここで、nは配列のサイズです。配列の最後のインデックスに到達するための最小ステップ数を見つける必要があります。

したがって、入力が次のような場合、

その場合、出力は3になります。インデックス0から4、3から9への3つのジャンプが必要です。

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

• 1つのマップを定義するm

• n：=arrのサイズ

• 初期化i：=0の場合、i

  • m [arr [i]]

    の最後にiを挿入します

• m [arr [i]]

  の最後にiを挿入します

• 訪問済みに0を挿入

• 1つのキューを定義するq

• 初期化レベル：=0の場合、qが空でない場合は、更新（レベルを1増やします）、do-

  • sz：=qのサイズ

  • szがゼロ以外の場合、各反復でszを1ずつ減らします-

    • curr：=qの最初の要素

    • qから要素を削除

    • currがn-1と同じ場合、

      • レベルを返す

    • i：=curr

    • i-1> =0であり、i-1が訪問されていない場合、-

      • i-1をqに挿入します

      • i-1をvisitedに挿入します

    • i +1ではなくi+1

      • i+1をqに挿入します

      • 訪問済みにi+1を挿入

    • 初期化j：=0の場合、j

      • （m [arr [curr]、j]）が訪問されていない場合、-

        • m [arr [curr]、j]をq

          に挿入します

        • m [arr [curr]、j]をvisited

          に挿入します

    • arr [curr]がmにない場合、-

      • m

        からarr[curr]を削除します

• -1を返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minJumps(vector<int>& arr) {
      map<int, vector<int> > m;
      int n = arr.size();
      for (int i = 0; i < n; i++) {
         m[arr[i]].push_back(i);
      }
      set<int> visited;
      visited.insert(0);
      queue<int> q;
      q.push(0);
      for (int lvl = 0; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            int curr = q.front();
            q.pop();
            if (curr == n - 1)
            return lvl;
            int i = curr;
            if (i - 1 >= 0 && !visited.count(i - 1)) {
               q.push(i - 1);
               visited.insert(i - 1);
            }
            if (i + 1 < n && !visited.count(i + 1)) {
               q.push(i + 1);
               visited.insert(i + 1);
            }
            for (int j = 0; j < m[arr[curr]].size(); j++) {
               if (!visited.count(m[arr[curr]][j])) {
                  q.push(m[arr[curr]][j]);
                  visited.insert(m[arr[curr]][j]);
               }
            }
            if (m.count(arr[curr])) {
               m.erase(arr[curr]);
            }
         }
      }
      return -1;
   }
};
main(){
   Solution ob;
   vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
   cout << (ob.minJumps(v));
}

入力

{20,-5,-5,25,20,5,5,5,1,25}

出力

3