C++ में आयत को न्यूनतम वर्गों से टाइल करना (Tiling a Rectangle with the Fewest Squares)

समस्या विवरण

एक n × m आकार का आयत दिया गया है। आयत को टाइल (ढकने) करने के लिए न्यूनतम पूर्णांक-भुजा वाले वर्गों (integer-sided squares) की संख्या ज्ञात करनी है।

उदाहरण

इनपुट: n = 2, m = 3

आउटपुट: 3

व्याख्या: तीन वर्गों की आवश्यकता होती है।

समाधान दृष्टिकोण (DFS + बैकट्रैकिंग + मेमोइजेशन)

वर्तमान भरे हुए क्षेत्र को ऊंचाई सरणी h[1..n] द्वारा दर्शाएं।
सबसे कम ऊंचाई वाली स्थिति pos ढूंढें।
वहां रखे जा सकने वाले सबसे बड़े वर्ग को आज़माएं (घटते क्रम में)।
वर्ग रखें, ऊंचाई सरणी अपडेट करें, पुनरावर्ती कॉल करें।
स्थिति को एन्कोड करके मेमोइजेशन (कैशिंग) करें।
प्रूनिंग: यदि वर्तमान गिनती ≥ सर्वश्रेष्ठ परिणाम, तो वापस लौटें।

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    map<long long, int> memo;
    int best = INT_MAX;
    
    void dfs(int n, int m, vector<int>& h, int cnt) {
        if (cnt >= best) return;
        
        bool full = true;
        int pos = -1, minH = INT_MAX;
        for (int i = 1; i <= n; i++) {
            if (h[i] < m) full = false;
            if (h[i] < minH) { minH = h[i]; pos = i; }
        }
        if (full) { best = min(best, cnt); return; }
        
        // स्थिति एन्कोडिंग
        long long key = 0, base = m + 1;
        for (int i = 1; i <= n; i++) {
            key += h[i] * base;
            base *= (m + 1);
        }
        if (memo.count(key) && memo[key] <= cnt) return;
        memo[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 sz = j - pos + 1;
            vector<int> next = h;
            for (int k = pos; k <= j; k++) next[k] += sz;
            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, 0);
        dfs(n, m, h, 0);
        return best;
    }
};

int main() {
    Solution ob;
    cout << ob.tilingRectangle(2, 3);
    return 0;
}