মান লিজিয়ে, ২ সারি এবং n কলাম যুক্ত একটি গ্রিড দেওয়া আছে। গ্রিডটি n টি বোর্ড দিয়ে ঢাকা থাকবে যেন কোনো বোর্ড অন্য বোর্ডের ওপর না পড়ে। বোর্ডগুলো তিনটি রঙের যেকোনো একটি (লাল, নীল, সবুজ) দিয়ে রঙ করতে হবে। পরস্পর সংলগ্ন দুটি বোর্ড একই রঙে রঙ করা যাবে না এবং প্রয়োজন না হলে সব রঙ ব্যবহার করা বাধ্যতামূলক নয়। গ্রিডের কনফিগারেশন 'grid' অ্যারেতে দেওয়া আছে, যেখানে প্রতিটি বোর্ড একই ইংরেজি অক্ষর দিয়ে প্রকাশ করা হয়েছে এবং ভিন্ন বোর্ডের জন্য ভিন্ন অক্ষর ব্যবহার করা হয়েছে। আমাদের লক্ষ্য হলো বোর্ডগুলো রঙ করার কতগুলো উপায় আছে তা বের করা।
যেমন, ইনপুট হলে n = 4, grid = {"abbd", "accd"}, তবে আউটপুট হবে 6।
প্রদত্ত শর্তাবলী মেনে বোর্ডগুলো রঙ করার ৬টি ভিন্ন উপায় রয়েছে।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
MODVAL := 10^9 + 7 একটি s অ্যারে সংজ্ঞায়িত করুন i := 0 দিয়ে আরম্ভ করুন, i < n হলে: if grid[0, i] == grid[1, i], তবে: s-র শেষে ১ যোগ করুন (i ১ বাড়িয়ে) অন্যথায়: s-র শেষে ২ যোগ করুন i := i + 2 একটি tvec অ্যারে সংজ্ঞায়িত করুন if s[0] == 1, তবে: tvec[0] := 3 অন্যথায়: tvec[0] := 6 i := 1 দিয়ে আরম্ভ করুন, i < s-র আকার হলে, (i ১ বাড়িয়ে) করুন: if s[i-1] == 2 এবং s[i] == 2, তবে: tvec[i] := tvec[i-1] * 3 mod MODVAL if s[i-1] == 2 এবং s[i] == 1, তবে: tvec[i] := tvec[i-1] if s[i-1] == 1 এবং s[i] == 2, তবে: tvec[i] := tvec[i-1] * 2 mod MODVAL if s[i-1] == 1 এবং s[i] == 1, তবে: tvec[i] := tvec[i-1] * 2 mod MODVAL tvec[s-র আকার - 1] রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int solve(int n, vector<string> grid){ int MODVAL = 1e9 + 7; vector<int> s; for (int i = 0; i < n;) { if (grid[0][i] == grid[1][i]) { s.push_back(1); i++; } else { s.push_back(2); i += 2; } } vector<int> tvec(s.size()); if (s[0] == 1) tvec[0] = 3; else tvec[0] = 6; for (int i = 1; i < (int)s.size(); i++) { if (s[i - 1] == 2 && s[i] == 2) tvec[i] = tvec[i - 1] * 3 % MODVAL; if (s[i - 1] == 2 && s[i] == 1) tvec[i] = tvec[i - 1]; if (s[i - 1] == 1 && s[i] == 2) tvec[i] = tvec[i - 1] * 2 % MODVAL; if (s[i - 1] == 1 && s[i] == 1) tvec[i] = tvec[i - 1] * 2 % MODVAL; } return tvec[s.size() - 1]; } int main() { int n = 4; vector <string> grid = {"abbd", "accd"}; cout<< solve(n, grid); return 0; } ইনপুট
4, {"abbd", "accd"} আউটপুট
6
