铺瓷砖

题目

1240. 铺瓷砖

---

你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。

房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。

假设正方形瓷砖的规格不限，边长都是整数。

请你帮设计师计算一下，最少需要用到多少块方形瓷砖？

示例 1：

输入：n = 2, m = 3
输出：3
解释：3 块地砖就可以铺满卧室。
     2 块 1x1 地砖
     1 块 2x2 地砖

示例 2：

输入：n = 5, m = 8
输出：5

示例 3：

输入：n = 11, m = 13
输出：6

提示：

• 1 <= n <= 13
• 1 <= m <= 13

题解

方法一：

思路

这是一道深搜好题，可以学到很多剪枝技巧。

虽然本题数据量很小，但是单纯的暴力深搜仍然是会超时的。

我们先看如何暴力然后再次基础上优化。

先初始化一个n*m的矩阵01矩阵，如果矩阵中某个位置为1则说明这个位置被某个正方形覆盖了。

接着设计一个递归函数，如果01矩阵全为1，则递归终止。
否则找到第一个值为0的位置(x,y)，尝试覆盖行坐标范围为[x, x+k)列坐标范围为[y,y+k)的矩形，首先尝试用大小为k=1的正方形覆盖，若覆盖没有产生冲突则调用递归函数处理新局面的01矩阵。
在调用递归结束后撤销覆盖，然后尝试用大小为k=2的正方形覆盖，依此类推。当边长为k的正方形产生越界或者覆盖冲突，后续更大的正方形也没有必要尝试了。
每次遇到递归终止时，维护所使用的正方形最小数目。

这个思路的代码实现如下，这是一个非常暴力的实现，没有任何优化。妥妥的超时。

class Solution {
public:
    int tilingRectangle(int n, int m) {
        vector<vector<int>> g(n,vector<int>(m, 0));
        auto rs = [&](int x, int y, int c, int v) {
            for (int i=0; i<c; i++) {
                for (int j=0; j<c; j++) {
                    if (x+i>=n || y+j>=m || g[x+i][y+j] == v) return false;
                }
            }
            for (int i=0; i<c; i++) {
                for (int j=0; j<c; j++) {
                    g[x+i][y+j] = v;
                }
            }
            return true;
        };
        int ans = n*m;
        function<void(int,int)> dfs = [&](int cnt, int one) {
            if (one == n*m) {
                ans = min(ans, cnt);
                return ;
            }
            for (int i=0; i<n; i++) {
                for (int j=0; j<m; j++) {
                    if (g[i][j] == 0) {
                        for (int k=1; k<=min(n-i,m-j); k++) {
                            if (!rs(i,j,k,1)) break;
                            // cout << cnt << " " <<  i << " " << j << endl;
                            dfs(cnt+1, one+k*k);
                            rs(i,j,k,0);
                        }
                        break;
                    }
                }
            }
        };
        dfs(0, 0);
        return ans;
    }
};

根据多次尝试发现至少要解决三个问题才能通过。

首先递归体复杂度过高。递归函数在找0位置时所耗费的时间过高，在递归体中每次需要双重for来定位到0，实际上如果在一次递归尝覆盖了行坐标范围为[x,x+k)列坐标范围为[y,y+k)的矩形。那么新的一个0位置的点(a,b)满足a*m+b > x*m+y+k。双重for存在大量无意义的遍历，我们可以在递归时添加参数表示当前作为正方形起始的位置。

然后就是基于当前最优状态的剪枝。在递归时发现已经使用的正方形个数大于等于已维护的最小值，则继续搜索无意义。

最后就是贪心策略的启发式引导，这能快速找到一个比较优的解，这能极大发挥基于当前最优状态的剪枝的作用。如果我们在搜索时优先使用大的正方形，那么最后如果能完全覆盖，那么得到的使用正方形数目肯定是比较小的，后续的剪枝效果会更明显。

代码

class Solution {
public:
    int tilingRectangle(int n, int m) {
        vector<vector<int>> g(n,vector<int>(m, 0));
        auto rs = [&](int x, int y, int c, int v) {
            for (int i=0; i<c; i++) {
                for (int j=0; j<c; j++) {
                    if (x+i>=n || y+j>=m || g[x+i][y+j] == v) return false;
                }
            }
            for (int i=0; i<c; i++) {
                for (int j=0; j<c; j++) {
                    g[x+i][y+j] = v;
                }
            }
            return true;
        };
        int ans = n*m;
        function<void(int,int,int,int)> dfs = [&](int x, int y, int cnt, int one) {
            // cout << x << " " << y << " " << cnt << " " << one << endl;
            if (cnt >= ans) return ;
            if (one == n*m) {
                ans = min(ans, cnt);
                return ;
            }
            if (x == n) return ;
            else if (y == m) {
                dfs(x+1, 0, cnt, one);
            } 
            else if (g[x][y] == 1) {
                dfs(x, y+1,cnt,one);
            }
            else {
                for (int k=min(n-x,m-y); k>=1; k--) {
                    if (!rs(x,y,k,1)) continue;
                    // cout << cnt << " " <<  i << " " << j << endl;
                    dfs(x, y+k, cnt+1, one+k*k);
                    rs(x,y,k,0);
                }
            }
        };
        dfs(0, 0, 0, 0);
        return ans;
    }
};