मान लीजिए, हमें एक ग्रिड दिया गया है जिसमें 2 पंक्तियाँ और n कॉलम हैं। ग्रिड को n बोर्डों द्वारा कवर किया जाना चाहिए, बिना एक बोर्ड दूसरे पर चढ़े। अब, बोर्डों को लाल, नीले और हरे रंग के बीच किसी एक रंग से रंगना होगा। एक दूसरे से सटे दो बोर्ड एक ही रंग से रंगे नहीं जा सकते हैं और यदि आवश्यक न हो तो सभी रंगों का उपयोग करने की आवश्यकता नहीं है। ग्रिड का विन्यास 'ग्रिड' सरणी में दिया गया है, जहां ग्रिड में एक विशेष बोर्ड को एक ही अंग्रेजी अक्षर का उपयोग करके दर्शाया जाता है और विभिन्न बोर्डों को विभिन्न अंग्रेजी अक्षरों का उपयोग करके दर्शाया जाता है। हमें यह पता लगाना होगा कि बोर्डों को कितने तरीकों से रंगा जा सकता है।
इसलिए, यदि इनपुट n =4, ग्रिड ={"abbd", "accd"} जैसा है, तो आउटपुट 6 होगा।
दिए गए मानदंड को पूरा करने वाले बोर्डों को रंगने के 6 अलग-अलग तरीके हैं।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
MODVAL := 10^9 + 7
Define an array s
for initialize i := 0, when i < n, do:
if grid[0, i] is same as grid[1, i], then:
insert 1 at the end of s
(increase i by 1)
Otherwise,
insert 2 at the end of s
i := i + 2
Define an array tvec
if s[0] is same as 1, then:
tvec[0] := 3
Otherwise,
tvec[0] := 6
for initialize i := 1, when i < size of s, update (increase i by 1), do:
if s[i - 1] is same as 2 and s[i] is same as 2, then:
tvec[i] := tvec[i - 1] * 3 mod MODVAL
if s[i - 1] is same as 2 and s[i] is same as 1, then:
tvec[i] := tvec[i - 1]
if s[i - 1] is same as 1 and s[i] is same as 2, then:
tvec[i] := tvec[i - 1] * 2 mod MODVAL
if s[i - 1] is same as 1 and s[i] is same as 1, then:
tvec[i] := tvec[i - 1] * 2 mod MODVAL
return tvec[size of 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