Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

2×n ग्रिड में बोर्ड्स को रंगने के तरीकों की संख्या ज्ञात करने का C++ प्रोग्राम


मान लीजिए हमारे पास 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
  1. ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल स्वयं और अपने दाएँ, बाएँ, ऊपर, नीचे की सेल्स को रोशन करता है। प्रकाश सेल्स के माध्यम से चमकता है जब तक कि कोई बाधा सेल इसे न रोक दे। बाधा सेल न तो रोशन हो सकती है और न ही प्रकाश को गुजरने देती ह

  1. ग्रिड में पथ बनाने के लिए ब्लॉक की जाने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में पथ बनाने के लिए ब्लॉक की जाने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड है। रोबोट सेल (0, 0) पर है और उसे (h-1, w-1) तक पहुँचना है। ग्रिड में दो प्रकार की सेल्स हैं: ब्लॉक और अनब्लॉक। रोबोट अनब्लॉक सेल्स से गुजर सकता है लेकिन ब्लॉक सेल्स से नहीं। रोबोट चार दिशाओं में जा सकता है: बाएँ, दाएँ, ऊपर, नीचे। लेकिन रोबोट किसी सेल से दूसरी सेल म

  1. N × 3 ग्रिड को रंगने के तरीकों की संख्या - C++ प्रोग्राम N × 3 ग्रिड को रंगने के तरीकों की संख्या - C++ प्रोग्राम

    मान लीजिए हमारे पास एक ग्रिड है जिसका आकार n x 3 है और हम ग्रिड के प्रत्येक सेल को तीन रंगों में से ठीक एक से रंगना चाहते हैं। यहां उपयोग किए जाने वाले रंग लाल, पीला और हरा हैं।अब एक प्रतिबंध है, कि कोई दो आसन्न सेल एक ही रंग के नहीं हो सकते। हमारे पास ग्रिड की n संख्या में पंक्तियाँ हैं। अंत में, ह