C++ में सबसे कम वर्गों के साथ एक आयत को टाइल करना

मान लीजिए हमारे पास n x m आकार का एक आयत है। हमें आयतों को टाइल करने वाले पूर्णांकों की पक्षीय वर्ग वस्तुओं की न्यूनतम संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट n =2 और m =3 जैसा है, तो

तब आउटपुट 3 होगा, क्योंकि हमें तीन ब्लॉक चाहिए।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक नक्शा परिभाषित करें मी

• रेस :=inf

• फ़ंक्शन dfs() को परिभाषित करें, इसमें n, m, एक सरणी h, cnt,

  लगेगा

• अगर cnt>=res, तो −

  • वापसी

• पूर्ण:=सत्य

• स्थिति :=-1, minH :=inf

• इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • यदि h[i]

    • पूर्ण है:=असत्य

  • यदि h[i]

    • मिनएच:=एच[i]

    • स्थिति :=मैं

• यदि isFul गैर-शून्य है, तो -

  • रेस :=न्यूनतम रेस और सीएनटी

  • वापसी

• कुंजी :=0

• आधार :=एम + 1

• इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • कुंजी:=कुंजी + एच [i] * आधार

  • आधार:=आधार * (एम + 1)

• यदि कुंजी s और s[key] <=cnt में है, तो -

  • वापसी

• एस [कुंजी]:=सीएनटी

• अंत:=स्थिति

• जबकि (अंत + 1 <=n और h[end + 1] h[pos] और (end + 1 - pos + 1 + minH) के समान है

• <=एम), करो -

  • (अंत में 1 से बढ़ाएं)

• प्रारंभ करने के लिए j :=end, जब j>=pos, अपडेट करें (j को 1 से घटाएं), करें -

  • curH :=j - pos + 1

  • आकार n + 1 के आगे एक सरणी परिभाषित करें

  • इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

    • अगला[i] :=h[i]

  • इनिशियलाइज़ k :=pos के लिए, जब k <=j, अपडेट करें (k को 1 से बढ़ाएँ), करें -

    • अगला [के]:=अगला [के] + वक्र

  • dfs(n, m, next, cnt + 1)

• मुख्य विधि से निम्न कार्य करें -

• यदि n, m के समान है, तो -

  • वापसी 1

• अगर n> मी, तो

  • स्वैप (एन, एम)

• आकार n + 1

  . के एक सरणी h को परिभाषित करें

• dfs(n, m, h, 0)

• रिटर्न रेस

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map<int, int> s;
   int res = INT_MAX;
   void dfs(int n, int m, vector<int> h, int cnt){
      if (cnt >= res)
         return;
      bool isFull = true;
      int pos = -1, minH = INT_MAX;
      for (int i = 1; i <= n; i++) {
         if (h[i] < m)
            isFull = false;
         if (h[i] < minH) {
            minH = h[i];
            pos = i;
         }
      }
      if (isFull) {
         res = min(res, cnt);
         return;
      }
      long key = 0;
      long base = m + 1;
      for (int i = 1; i <= n; i++) {
         key += h[i] * base;
         base *= m + 1;
      }
      if (s.find(key) != s.end() && s[key] <= cnt)
         return;
      s[key] = cnt;
      int end = pos;
      while (end + 1 <= n && h[end + 1] == h[pos] && (end + 1 - pos + 1 + minH) <= m)
      end++;
      for (int j = end; j >= pos; j--) {
         int curH = j - pos + 1;
         vector<int> next(n + 1);
         for (int i = 1; i <= n; i++)
            next[i] = h[i];
         for (int k = pos; k <= j; k++) {
            next[k] += curH;
         }
         dfs(n, m, next, cnt + 1);
      }
   }
   int tilingRectangle(int n, int m){
      if (n == m)
         return 1;
      if (n > m)
         swap(n, m);
      vector<int> h(n + 1);
      dfs(n, m, h, 0);
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.tilingRectangle(2, 3));
}

इनपुट

2,3

आउटपुट

3