LeetCode 1240. 铺瓷砖

字数 1989 2025-12-07 18:59:08

LeetCode 1240. 铺瓷砖

题目描述
你是一位贴瓷砖的工人，需要为一个 n x m 大小的墙面铺上正方形瓷砖。每个瓷砖的尺寸是 1 x 1，且墙面必须完全被覆盖。由于墙面可能存在瑕疵，你需要用最少数量的正方形瓷砖来铺满整个墙面。这里的“正方形瓷砖”边长可以是任意整数（即边长可以为 1、2、3...），目标是使用尽可能少的正方形瓷砖覆盖整个 n x m 的矩形墙面。
给定两个整数 n 和 m（1 <= n, m <= 13），返回铺满墙面所需的最小瓷砖数量。

示例：
输入：n = 2, m = 3
输出：3
解释：一种铺法是用 2x2、1x1、1x1 三块瓷砖，或者三个 1x2 和 1x1 的组合，但最少的正方形瓷砖数是 3。

解题思路
这是一个经典的“铺正方形瓷砖”问题，本质上是将一个大矩形分割成尽可能少的不同大小的正方形。由于数据范围较小（最大 13x13），可以使用深度优先搜索（DFS）配合回溯和剪枝来求解。

核心思路如下：

用一个二维数组 grid 表示墙面，初始所有位置未被覆盖（例如用 0 表示未覆盖，正整数表示已被某块瓷砖覆盖）。
从左到右、从上到下寻找第一个未被覆盖的位置 (r, c)。
尝试在该位置放置所有可能边长的正方形瓷砖，边长从大到小尝试（贪心思想，大正方形可能减少数量）。
放置瓷砖后，递归地继续寻找下一个空位，直到所有位置被覆盖，记录所用瓷砖数。
通过回溯尝试不同选择，并利用当前最优解进行剪枝。

详细步骤

步骤 1：定义状态和变量

grid[r][c]：表示位置 (r, c) 是否已被覆盖。可以用一个整数表示被哪块瓷砖覆盖（例如瓷砖编号），或简单用布尔值。这里为了回溯方便，可用整数 0 表示未覆盖，正整数表示被覆盖。
cnt：当前已使用的瓷砖数。
best：全局最小瓷砖数，初始设为 n*m（最坏情况全用 1x1）。

步骤 2：递归搜索函数设计
函数 dfs(r, c, cnt) 表示从位置 (r, c) 开始继续铺瓷砖。

如果 cnt >= best，直接返回（剪枝：当前已用的瓷砖数已经不小于已知最优解）。
如果 r == n，说明所有行已处理完，更新 best = min(best, cnt) 并返回。
如果 c == m，说明当前行已处理完，递归到下一行第一个位置：dfs(r+1, 0, cnt)。
如果 grid[r][c] 已被覆盖，则递归到下一个位置：dfs(r, c+1, cnt)。
否则，在 (r, c) 放置一个正方形，尝试所有可能的边长 len，从大到小尝试（从 min(n-r, m-c) 到 1）：
a. 检查以 (r, c) 为左上角、边长为 len 的正方形区域是否都未被覆盖。
b. 如果未被覆盖，则“覆盖”这个区域（例如标记为 cnt+1），递归调用 dfs(r, c+len, cnt+1)。
c. 回溯：将刚才覆盖的区域恢复为未覆盖状态。

步骤 3：优化剪枝

最优性剪枝：如上所述，当 cnt >= best 时停止。
贪心尝试顺序：从大到小尝试正方形边长，可能更快接近最优解。
提前找到空位：每次递归从当前 (r, c) 开始向右、向下找第一个空位，而不是固定顺序，可以减少递归层数。

步骤 4：初始化与启动

初始化 grid 全为 0。
初始调用 dfs(0, 0, 0)。
最终返回 best。

示例推演（n=2, m=3）
初始网格：

0 0 0
0 0 0

在 (0,0) 尝试边长 2 的正方形，但高度只有 2，宽度 3，最大边长 min(2,3)=2。检查 (0,0)-(1,1) 区域为空，可以放置。
放置后网格（假设用 1 标记）：
```
1 1 0
1 1 0
```
递归到 (0,2)，继续尝试。
在 (0,2) 只能放 1x1（因为高度只剩 2 但宽度只剩 1，最大边长 1）。
放置后：
```
1 1 2
1 1 0
```
递归到 (1,2)，放 1x1：
```
1 1 2
1 1 3
```
所有格覆盖，瓷砖数 = 3，记录 best=3。
回溯尝试其他方案。比如在 (0,0) 放边长 1 的正方形，后续会需要更多瓷砖，不会优于 3。

最终结果 = 3。

复杂度分析

状态空间很大，但剪枝有效。最坏情况是指数级，但 n,m ≤ 13 实际可接受。
利用贪心顺序和最优剪枝，通常可以在较短时间内得到解。

实现提示

可以用一维数组表示网格，每个位置用整型标记是否覆盖。
检查正方形区域是否全为空时，可以预先判断，避免每次循环检查。
在递归前，如果当前空位 (r,c) 之后，剩余面积除以当前最大可能正方形面积仍然无法优于 best，可提前剪枝（进一步优化）。

这个题目结合了回溯、剪枝、贪心尝试顺序，是搜索类问题的一个经典变种。

LeetCode 1240. 铺瓷砖题目描述你是一位贴瓷砖的工人，需要为一个 n x m 大小的墙面铺上正方形瓷砖。每个瓷砖的尺寸是 1 x 1 ，且墙面必须完全被覆盖。由于墙面可能存在瑕疵，你需要用最少数量的正方形瓷砖来铺满整个墙面。这里的“正方形瓷砖”边长可以是任意整数（即边长可以为 1、2、3...），目标是使用尽可能少的正方形瓷砖覆盖整个 n x m 的矩形墙面。给定两个整数 n 和 m （ 1 <= n, m <= 13 ），返回铺满墙面所需的最小瓷砖数量。示例：输入：n = 2, m = 3 输出：3 解释：一种铺法是用 2x2、1x1、1x1 三块瓷砖，或者三个 1x2 和 1x1 的组合，但最少的正方形瓷砖数是 3。解题思路这是一个经典的“铺正方形瓷砖”问题，本质上是将一个大矩形分割成尽可能少的不同大小的正方形。由于数据范围较小（最大 13x13），可以使用深度优先搜索（DFS）配合回溯和剪枝来求解。核心思路如下：用一个二维数组 grid 表示墙面，初始所有位置未被覆盖（例如用 0 表示未覆盖，正整数表示已被某块瓷砖覆盖）。从左到右、从上到下寻找第一个未被覆盖的位置 (r, c) 。尝试在该位置放置所有可能边长的正方形瓷砖，边长从大到小尝试（贪心思想，大正方形可能减少数量）。放置瓷砖后，递归地继续寻找下一个空位，直到所有位置被覆盖，记录所用瓷砖数。通过回溯尝试不同选择，并利用当前最优解进行剪枝。详细步骤步骤 1：定义状态和变量 grid[r][c] ：表示位置 (r, c) 是否已被覆盖。可以用一个整数表示被哪块瓷砖覆盖（例如瓷砖编号），或简单用布尔值。这里为了回溯方便，可用整数 0 表示未覆盖，正整数表示被覆盖。 cnt ：当前已使用的瓷砖数。 best ：全局最小瓷砖数，初始设为 n*m （最坏情况全用 1x1）。步骤 2：递归搜索函数设计函数 dfs(r, c, cnt) 表示从位置 (r, c) 开始继续铺瓷砖。如果 cnt >= best ，直接返回（剪枝：当前已用的瓷砖数已经不小于已知最优解）。如果 r == n ，说明所有行已处理完，更新 best = min(best, cnt) 并返回。如果 c == m ，说明当前行已处理完，递归到下一行第一个位置： dfs(r+1, 0, cnt) 。如果 grid[r][c] 已被覆盖，则递归到下一个位置： dfs(r, c+1, cnt) 。否则，在 (r, c) 放置一个正方形，尝试所有可能的边长 len ，从大到小尝试（从 min(n-r, m-c) 到 1）： a. 检查以 (r, c) 为左上角、边长为 len 的正方形区域是否都未被覆盖。 b. 如果未被覆盖，则“覆盖”这个区域（例如标记为 cnt+1 ），递归调用 dfs(r, c+len, cnt+1) 。 c. 回溯：将刚才覆盖的区域恢复为未覆盖状态。步骤 3：优化剪枝最优性剪枝：如上所述，当 cnt >= best 时停止。贪心尝试顺序：从大到小尝试正方形边长，可能更快接近最优解。提前找到空位：每次递归从当前 (r, c) 开始向右、向下找第一个空位，而不是固定顺序，可以减少递归层数。步骤 4：初始化与启动初始化 grid 全为 0。初始调用 dfs(0, 0, 0) 。最终返回 best 。示例推演（n=2, m=3）初始网格：在 (0,0) 尝试边长 2 的正方形，但高度只有 2，宽度 3，最大边长 min(2,3)=2。检查 (0,0)-(1,1) 区域为空，可以放置。放置后网格（假设用 1 标记）：递归到 (0,2)，继续尝试。在 (0,2) 只能放 1x1（因为高度只剩 2 但宽度只剩 1，最大边长 1）。放置后：递归到 (1,2)，放 1x1：所有格覆盖，瓷砖数 = 3，记录 best=3。回溯尝试其他方案。比如在 (0,0) 放边长 1 的正方形，后续会需要更多瓷砖，不会优于 3。最终结果 = 3。复杂度分析状态空间很大，但剪枝有效。最坏情况是指数级，但 n,m ≤ 13 实际可接受。利用贪心顺序和最优剪枝，通常可以在较短时间内得到解。实现提示可以用一维数组表示网格，每个位置用整型标记是否覆盖。检查正方形区域是否全为空时，可以预先判断，避免每次循环检查。在递归前，如果当前空位 (r,c) 之后，剩余面积除以当前最大可能正方形面积仍然无法优于 best，可提前剪枝（进一步优化）。这个题目结合了回溯、剪枝、贪心尝试顺序，是搜索类问题的一个经典变种。