Mã C ++ để kiểm tra châu chấu có thể đạt được mục tiêu hay không

Giả sử chúng ta có một chuỗi S kích thước n và một số k khác. Chuỗi chứa bốn loại ký tự. Xem xét có ít ô, một con châu chấu muốn nhảy để tiếp cận mục tiêu. Tính cách '.' có nghĩa là ô tương ứng trống, ký tự '#' có nghĩa là ô tương ứng chứa chướng ngại vật và châu chấu không thể nhảy đến đó. 'G' có nghĩa là con châu chấu bắt đầu ở vị trí này và 'T' có nghĩa là ô đích. Con châu chấu có thể nhảy chính xác k ô ra khỏi vị trí hiện tại của nó. Chúng tôi phải kiểm tra xem con châu chấu có thể nhảy tới mục tiêu hay không.

Vì vậy, nếu đầu vào giống như S ="# G # T #"; k =2, thì kết quả đầu ra sẽ là True, vì từ G đến T cách đó 2 ô và k là 2 nên châu chấu có thể đến đó chỉ bằng một bước nhảy.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

"#G#T#", 2

Đầu ra

1