1240.铺瓷砖

链接：1240.铺瓷砖
难度：Hard
标签：回溯
简介：房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。假设正方形瓷砖的规格不限，边长都是整数。请你帮设计师计算一下，最少需要用到多少块方形瓷砖？。

题解 1 - cpp

• 编辑时间：2023-06-08
• 执行用时：8ms
• 内存消耗：6MB
• 编程语言：cpp
• 解法介绍：dfs，储存已经遍历过的点。

class Solution {
public:
    int tilingRectangle(int n, int m) {
        int res = INT_MAX, list[20] = {0};
        function<void(int, int, int)> dfs = [&](int i, int j, int cnt) {
            if (i == n) {
                res = min(res, cnt);
            } else if (j == m) {
                dfs(i + 1, 0, cnt);
            } else if (list[i] & (1 << j)) {
                dfs(i, j + 1, cnt);
            } else if (cnt < res) {
                int ncnt = 0, mcnt = 0;
                for (int p = i; p < n && !(list[p] & (1 << j)); p++) ncnt++;
                for (int p = j; p < m && !(list[i] & (1 << p)); p++) mcnt++;
                int nmcnt = min(ncnt, mcnt);
                for (int ccnt = nmcnt; ccnt >= 1; ccnt--) {
                    for (int p = i; p < i + ccnt; p++) list[p] |= (((1 << ccnt) - 1) << j);
                    dfs(i, j + ccnt, cnt + 1);
                    for (int p = i; p < i + ccnt; p++) list[p] &= ~(((1 << ccnt) - 1) << j);
                }
            }
        };
        dfs(0, 0, 0);
        return res;
    }
};