รหัส C++ ตรวจสอบตั๊กแตนสามารถเข้าถึงเป้าหมายได้หรือไม่

สมมติว่าเรามีสตริง S ขนาด n และอีกจำนวนหนึ่งคือ 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