मान लीजिए हमारे पास 2 पंक्तियों और n स्तंभों वाला एक ग्रिड है जिसे n बोर्ड्स से ढका जाना है बिना ओवरलैप के। प्रत्येक बोर्ड को लाल, नीला या हरा रंग से रंगा जाना है। आसन्न बोर्ड्स का रंग समान नहीं हो सकता। सभी रंगों का उपयोग करना आवश्यक नहीं है। ग्रिड की विन्यास 'grid' सरणी में दी गई है जहाँ समान अक्षर एक ही बोर्ड को दर्शाता है। हमें बोर्ड्स को रंगने के वैध तरीकों की संख्या ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है n = 4, grid = {"abbd", "accd"}, तो आउटपुट 6 होगा।
दिए गए मानदंड को पूरा करने वाले 6 अलग-अलग रंग संयोजन हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
MODVAL := 10^9 + 7
एक सरणी s परिभाषित करें
i := 0 से प्रारंभ करें, जब i < n:
यदि grid[0][i] == grid[1][i], तो:
s के अंत में 1 डालें
i := i + 1
अन्यथा:
s के अंत में 2 डालें
i := i + 2
एक सरणी tvec परिभाषित करें
यदि s[0] == 1, तो tvec[0] := 3
अन्यथा tvec[0] := 6
i := 1 से प्रारंभ करें, जब i < s का आकार, i को 1 से बढ़ाते हुए:
यदि s[i-1] == 2 और s[i] == 2, तो:
tvec[i] := (tvec[i-1] * 3) % MODVAL
यदि s[i-1] == 2 और s[i] == 1, तो:
tvec[i] := tvec[i-1]
यदि s[i-1] == 1 और s[i] == 2, तो:
tvec[i] := (tvec[i-1] * 2) % MODVAL
यदि s[i-1] == 1 और s[i] == 1, तो:
tvec[i] := (tvec[i-1] * 2) % 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