ধরুন আমাদের 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