カエルが家に着くための最小ジャンプを見つけるためのC++コード

nビットの2進文字列Sと別の数dがあるとします。数直線上で、カエルはポイント1から開始してポイントnに到達しようとしています。カエルはd以下の距離で右にジャンプできます。ユリの花がある場合は1からnまでの各ポイントについて、1としてマークされ、ない場合は0としてマークされます。カエルはユリのいるポイントでのみジャンプできます。カエルがnに到達するために必要なジャンプの最小数を見つける必要があります。不可能な場合は、-1を返します。

したがって、入力がS="10010101"のような場合。 d =4の場合、出力は2になります。これは、位置1から4にジャンプし、次にインデックス8（n）にジャンプするためです。

ステップ

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

n := size of s
x := 0
y := 0
while (x < n - 1 and y <= n), do:
   if s[x] is same as '1', then:
      x := x + d
      increase y by 1
   Otherwise
      (decrease x by 1)
if y >= n, then:
   return -1
Otherwise
   return y

例

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

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int d){
   int n = s.size();
   int x = 0, y = 0;
   while (x < n - 1 && y <= n){
      if (s[x] == '1')
         x += d, ++y;
      else
         --x;
   }
   if (y >= n)
      return -1;
   else
      return y;
}
int main(){
   string S = "10010101";
   int d = 4;
   cout << solve(S, d) << endl;
}

入力

"10010101", 4

出力

2