সমস্যা বিবরণ
- দুই-মাত্রিক স্পেসে অনেক পয়েন্ট আছে যাদের নির্দিষ্ট ক্রমে ভিজিট করতে হবে।
- এক পয়েন্ট থেকে অন্যটিতে যেতে সবসময় সর্টেস্ট পথ বেছে নেওয়া হয় এবং পথ সেগমেন্টগুলো গ্রিড লাইনের সাথে অ্যালাইনড থাকে।
- দেওয়া পথ থেকে ন্যূনতম কতগুলো পয়েন্ট (স্টপ) দরকার তা বের করতে হবে।
অ্যালগরিদম
১. স্টপ ভিজিট করার সময় মুভমেন্টের প্যাটার্ন পর্যবেক্ষণ করে সমাধান করা যায়।
২. একটি পয়েন্ট থেকে অন্যটিতে সর্টেস্ট পথ নিলে maksimum দুটি ডিরেকশনে যেতে হয়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMinStops(string path) {
int n = path.length();
map<char, int> directionMap;
int stops = 1;
for (int i = 0; i < n; ++i) {
char direction = path[i];
directionMap[direction] = 1;
if ((directionMap['L'] && directionMap['R']) ||
(directionMap['U'] && directionMap['D'])) {
directionMap.clear();
++stops;
directionMap[direction] = 1;
}
}
return stops + 1;
}
int main() {
string path = "LLUUULLDD";
cout << "Minimum stops = " << getMinStops(path) << endl;
return 0;
}
আউটপুট
Minimum stops = 3
