C++-এ আয়তকে ন্যূনতম সংখ্যক বর্গ দিয়ে টাইল করা (Tiling a Rectangle with the Fewest Squares)

একটি n x m আকারের আয়ত দেওয়া আছে। এই আয়তকে পূর্ণসংখ্যা বাহু বিশিষ্ট বর্গাকার টুকরো দিয়ে ঢাকতে (tile) ন্যূনতম কতগুলো বর্গ লাগবে তা বের করতে হবে।

উদাহরণ

ইনপুট: n = 2, m = 3

আউটপুট: 3 (তিনটি বর্গ দরকার)

সমাধানের ধাপসমূহ

ব্যাকট্র্যাকিং (DFS) + প্রুনিং (pruning) + মেমোইজেশন ব্যবহার করুন।
প্রতিটি কলামের বর্তমান উচ্চতা ট্র্যাক করুন।
সবচোটে উঁচু কলাম খুঁজে সেখানে বর্গ বসান।
বর্গের আকার বড় থেকে ছোট দিকে ট্রাই করুন।
স্টেট হ্যাশ করে মেমোইজেশন করুন।

প্রোগ্রাম উদাহরণ

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

class Solution {
public:
    map<long, int> memo;
    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 (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 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;
    }
};

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

ইনপুট

2, 3