सी++ कोड टिड्डे की जांच के लिए लक्ष्य तक पहुंच सकता है या नहीं

मान लीजिए कि हमारे पास n आकार की एक स्ट्रिंग S और दूसरी संख्या k है। स्ट्रिंग में चार प्रकार के वर्ण होते हैं। गौर कीजिए कि कुछ कोशिकाएँ हैं, एक टिड्डा लक्ष्य तक पहुँचने के लिए कूदना चाहता है। चरित्र '।' इसका मतलब है कि संबंधित सेल खाली है, वर्ण '#' का मतलब है कि संबंधित सेल में एक बाधा है और टिड्डा वहां कूद नहीं सकता है। 'जी' का अर्थ है कि टिड्डा इसी स्थिति से शुरू होता है और, 'टी' का अर्थ है लक्ष्य कोशिका। टिड्डा अपनी वर्तमान स्थिति से ठीक k कोशिकाओं को दूर कूदने में सक्षम है। हमें यह जांचना होगा कि टिड्डा कूद कर निशाने पर आ सकता है या नहीं।

इसलिए, यदि इनपुट S ="#G#T#" जैसा है; k =2, तो आउटपुट ट्रू होगा, क्योंकि 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