バッタがターゲットに到達できるかどうかをチェックするC++コード

サイズnの文字列Sと別の数kがあるとします。文字列には4種類の文字が含まれています。セルが少ないと考えてください。バッタはターゲットに到達するためにジャンプしたいと考えています。キャラクター '。'対応するセルが空であることを意味します。文字「＃」は、対応するセルに障害物が含まれており、バッタがそこにジャンプできないことを意味します。 「G」はバッタがこの位置から始まることを意味し、「T」はターゲットセルを意味します。バッタは、現在の位置から正確にk個のセルをジャンプすることができます。バッタがターゲットにジャンプできるかどうかを確認する必要があります。

したがって、入力がS ="＃G＃T＃"のような場合; k =2の場合、出力はTrueになります。これは、GからTまでが2セル離れており、kが2であるため、バッタが1回のジャンプでそこに到達できるためです。

ステップ

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

n := size of S
x := position of 'G' in S
y := position of 'T' in S
if x > y, then:
   swap x and y
for initialize i := x, when i < y, update i := i + k, do:
   if S[i] is same as '#', then:
      Come out from the loop
if i is same as y, then:
   return true
Otherwise
   return false

例

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

#include <bits/stdc++.h>
using namespace std;
bool solve(string S, int k)
{
   int n = S.size();
   int i;
   int x = S.find('G');
   int y = S.find('T');
   if (x > y)
      swap(x, y);
   for (i = x; i < y; i += k)
   {
      if (S[i] == '#')
         break;
   }
   if (i == y)
      return true;
   else
      return false;
}
int main()
{
   string S = "#G#T#";
   int k = 2;
   cout << solve(S, k) << endl;
}

入力

"#G#T#", 2

出力

1