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

C++ में डोमिनो और ट्रोमिनो टाइलिंग


मान लीजिए हमारे पास दो प्रकार के आकार हैं, डोमिनो और ट्रोमिनो। उन्हें नीचे दिखाए अनुसार घुमाया जा सकता है:

C++ में डोमिनो और ट्रोमिनो टाइलिंग

एक टाइलिंग में, प्रत्येक वर्ग को एक टाइल द्वारा कवर किया जाना चाहिए। यहां दो टाइलिंग तभी अलग हैं जब बोर्ड पर दो 4-दिशात्मक आसन्न सेल हों जैसे कि उन टाइलिंग में से केवल एक में दोनों वर्ग एक टाइल द्वारा कब्जा किए गए हों।

दिया गया N, हमें कितने तरीकों से 2xN बोर्ड को टाइल करना है? उदाहरण के लिए, यदि इनपुट 3 है, तो आउटपुट 5 होगा। इसलिए व्यवस्थाएं [XYZ XXZ XYY XXY XYY] और [XYZ YYZ XZZ XYY XXY] हो सकती हैं, यहां अलग-अलग अक्षरों का उपयोग अलग-अलग टाइल्स के लिए किया जाता है।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • dp नामक एक सरणी बनाएं आकार N + 5 का, dp[1] := 1, dp[2] := 2 और dp[3] := 5 सेट करें
  • i को 4 से N तक लूप करें
    • dp[i] := 2*dp[i - 1] + dp[i - 3]
  • dp[N] लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; int add(int a, int b){    return ((a % MOD) + (b % MOD)) % MOD; } class Solution {    public:    int numTilings(int N) {       vector <int> dp(N + 5);       dp[1] = 1;       dp[2] = 2;       dp[3] = 5;       for(int i = 4; i <= N; i++){          dp[i] = add(2 * dp[i - 1], dp[i - 3]);       }       return dp[N];    } }; main(){    Solution ob;    cout << (ob.numTilings(3)); }

इनपुट

3

आउटपुट

5

  1. - C++ में सम सूचकांक पर सम संख्याएं और विषम सूचकांक पर विषम संख्याएं

    इस समस्या में, हमें आकार n की एक सरणी arr[] दी गई है जिसमें n/2 सम मान और n/2 विषम मान हैं। हमारा कार्य सम संख्याओं को सम सूचकांक पर और विषम संख्याओं को विषम सूचकांक पर रखने के लिए एक प्रोग्राम बनाना है। समस्या को समझने के लिए एक उदाहरण लेते हैं, इनपुट: arr[] = {5, 1, 6, 4, 3, 8} आउटपुट: arr[] = {6

  1. - C++ में दीवारें और गेट - BFS से निकटतम गेट की दूरी

    समस्या विवरण मान लीजिए हमारे पास एक m x n 2D ग्रिड है, जिसे इन तीन संभावित मानों से इनिशियलाइज़ किया गया है: -1 दीवार या बाधा के लिए 0 गेट के लिए INF अनंत के लिए अर्थात खाली कमरा यहां 2^31 - 1 = 2147483647 INF है क्योंकि हम मान सकते हैं कि गेट की दूरी 2147483647 से कम है। प्रत्येक खाली कमरे को उ

  1. C++ में वृत्त और आयत के ओवरलैप की जांच C++ में वृत्त और आयत के ओवरलैप की जांच

    मान लीजिए हमारे पास एक वृत्त है जिसे (त्रिज्या, xc, yc) से दर्शाया जाता है, जहां (xc, yc) केंद्र के निर्देशांक हैं। हमारे पास एक अक्ष-संरेखित आयत भी है जिसे (x1, y1, x2, y2) से दर्शाया जाता है, जहां (x1, y1) निचले-बाएं कोने के निर्देशांक हैं और (x2, y2) ऊपरी-दाएं कोने के निर्देशांक हैं। हमें जांचना