메뚜기가 대상에 도달할 수 있는지 확인하는 C++ 코드

크기가 n인 문자열 S와 또 다른 숫자 k가 있다고 가정합니다. 문자열에는 네 가지 유형의 문자가 포함됩니다. 세포가 거의 없다고 생각하면 메뚜기는 목표물에 도달하기 위해 점프하려고 합니다. 성격 '.' 해당 셀이 비어 있음을 의미하고 '#' 문자는 해당 셀에 장애물이 있어 메뚜기가 점프할 수 없음을 의미합니다. 'G'는 메뚜기가 이 위치에서 시작한다는 것을 의미하고, 'T'는 표적 세포를 의미한다. 메뚜기는 현재 위치에서 정확히 k 셀을 이동할 수 있습니다. 메뚜기가 과녁으로 점프할 수 있는지 확인해야 합니다.

따라서 입력이 S ="#G#T#"와 같으면; k =2이면 출력은 True가 됩니다. G에서 T까지는 2칸 떨어져 있고 k는 2이므로 메뚜기가 한 번의 점프로 거기에 도달할 수 있기 때문입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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