সমস্যা বিবরণ
দুটি স্ট্রিং str1 এবং str2 দেওয়া আছে, উভয়ে 'a' এবং 'b' ক্যারেক্টার রয়েছে। দোয়ের দৈর্ঘ্য সমান। দুটো স্ট্রিংয়ের মধ্যে একটি _ (খালি স্পেস) রয়েছে। নিচের অপারেশনগুলো কমপক্ষে কতবার করলে প্রথম স্ট্রিংটি দ্বিতীয় স্ট্রিংয়ে রূপান্তরিত হবে তা বের করতে হবে:
- যদি _ পজিশন i-তে থাকে, তবে _ কে i+1 বা i-1 পজিশনের ক্যারেক্টারসঙ্গে স্ব্যাপ করা যাবে
- যদি i+1 এবং i+2 পজিশনের ক্যারেক্টারগুলো ভিন্ন হয়, তবে _ কে i+1 বা i+2 পজিশনের ক্যারেক্টারসঙ্গে স্ব্যাপ করা যাবে
- একইভাবে, যদি i-1 এবং i-2 পজিশনের ক্যারেক্টারগুলো ভিন্ন হয়, তবে _ কে i-1 বা i-2 পজিশনের ক্যারেক্টারসঙ্গে স্ব্যাপ করা যাবে
যদি str1 = "aba_a" এবং str2 = "_baaa" হয়, তবে ২টি মুভ দরকার:
1. str1 = "ab_aa" (Swapped str1[2] with str1[3]) 2. str2 = "_baaa" (Swapped str1[0] with str1[2])
এলগরিদম
1. স্ট্রিংয়ের ওপর সাধারণ ব্রেডথ ফার্স্ট সার্চ (BFS) প্রয়োগ করুন। BFS-এর জন্য ব্যবহৃত কিউয়ের একটি এলিমেন্ট হবে pair str, pos যেখানে pos হল স্ট্রিং str-এ _-এর পজিশন। 2. একটি ম্যাপ 'vis' রক্ষা করুন যা স্ট্রিংকে কী এবং সেটি পাওয়ার ন্যূনতম মুভকে ভ্যালু হিসেবে রাখবে। 3. কিউ থেকে প্রতিটি স্ট্রিং str-এর জন্য, চারটি শর্ত অনুযায়ী নতুন স্ট্রিং tmp জেনারেট করুন এবং vis ম্যাপ আপডেট করুন: vis[tmp] = vis[str] + 1। 4. কিউ খালি না হওয়া পর্যন্ত বা প্রয়োজনীয় স্ট্রিং জেনারেট না হওয়া পর্যন্ত (tmp == B) উপরের ধাপগুলো পুনরাবৃত্তি করুন। 5. প্রয়োজনীয় স্ট্রিং জেনারেট হলে, vis[str] + 1 রিটার্ন করুন যা A কে B-তে পরিবর্তনের ন্যূনতম অপারেশন।
উদাহরণ কোড
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
int transformString(string str, string f) {
unordered_map<string, int> vis;
int n = str.length();
int pos = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == '_') {
pos = i;
break;
}
}
queue<pair<string, int> > q;
q.push({ str, pos });
vis[str] = 0;
while (!q.empty()) {
string ss = q.front().first;
int pp = q.front().second;
int dist = vis[ss];
q.pop();
if (pp > 0) {
swap(ss[pp], ss[pp - 1]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp - 1 });
}
swap(ss[pp], ss[pp - 1]);
}
if (pp < n - 1) {
swap(ss[pp], ss[pp + 1]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp + 1 });
}
swap(ss[pp], ss[pp + 1]);
}
if (pp > 1 && ss[pp - 1] != ss[pp - 2]) {
swap(ss[pp], ss[pp - 2]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp - 2 });
}
swap(ss[pp], ss[pp - 2]);
}
if (pp < n - 2 && ss[pp + 1] != ss[pp + 2]) {
swap(ss[pp], ss[pp + 2]);
if (!vis.count(ss)) {
if (ss == f) {
return dist + 1;
break;
}
vis[ss] = dist + 1;
q.push({ ss, pp + 2 });
}
swap(ss[pp], ss[pp + 2]);
}
}
return 0;
}
int main() {
string str1 = "aba_a";
string str2 = "_baaa";
cout << "Minimum required moves: " << transformString(str1, str2) << endl;
return 0;
}
আউটপুট
প্রোগ্রাম কম্পাইল ও এক্সিকিউট করলে নিচের আউটপুট পাওয়া যাবে:
Minimum required moves: 2
