मान लीजिए हमारे पास आकार 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
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing 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
