LeetCode1240 铺瓷砖

一、问题描述

给定一个大小为 n x m 的长方形，我们需要找出贴满这个矩形所需的整数边正方形的最小数量。例如，当 n = 2，m = 3 时，需要 3 个正方形来覆盖这个长方形，其中包括 2 个 1x1 的正方形和 1 个 2x2 的正方形。

二、解题思路

我们将使用回溯法来解决这个问题。回溯法是一种通过尝试所有可能的解决方案来找到最优解的算法。具体步骤如下：

1. 从长方形的左上角开始，尝试放置不同边长的正方形。
2. 每次放置一个正方形后，更新剩余未覆盖的区域。
3. 递归地继续在剩余区域放置正方形，直到整个长方形被覆盖。
4. 记录并更新使用正方形的最小数量。

三、代码实现

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// 定义一个全局变量来存储最小正方形数量
int ans;

// 回溯函数，尝试不同的正方形填充方式
void dfs(int *h, int n, int m, int squares) {
    // 如果当前使用的正方形数量已经超过了当前记录的最小数量，直接返回
    if (squares >= ans) return;
    int allFilled = 1;
    // 检查是否所有列都已经被填满
    for (int i = 0; i < n; i++) {
        if (h[i] < m) {
            allFilled = 0;
            break;
        }
    }
    // 如果所有列都被填满，更新最小正方形数量
    if (allFilled) {
        ans = squares;
        return;
    }
    // 找到当前高度最小的列
    int minH = INT_MAX;
    int minIndex = -1;
    for (int i = 0; i < n; i++) {
        if (h[i] < minH) {
            minH = h[i];
            minIndex = i;
        }
    }
    // 尝试不同边长的正方形进行填充
    for (int w = (n - minIndex < m - minH) ? n - minIndex : m - minH; w > 0; w--) {
        int canPlace = 1;
        // 检查是否可以放置边长为 w 的正方形
        for (int i = minIndex; i < minIndex + w; i++) {
            if (h[i] + w > m) {
                canPlace = 0;
                break;
            }
        }
        if (canPlace) {
            // 复制当前高度数组，用于回溯
            int *newH = (int *)malloc(n * sizeof(int));
            for (int i = 0; i < n; i++) {
                newH[i] = h[i];
            }
            for (int i = minIndex; i < minIndex + w; i++) {
                newH[i] += w;
            }
            // 递归调用 dfs 函数，继续尝试填充
            dfs(newH, n, m, squares + 1);
            free(newH);
        }
    }
}

// 主函数，计算贴满矩形所需的最小正方形数量
int tilingRectangle(int n, int m) {
    // 如果 n 和 m 相等，只需要一个正方形
    if (n == m) return 1;
    // 保证 n 小于等于 m，减少搜索空间
    if (n > m) {
        int temp = n;
        n = m;
        m = temp;
    }
    ans = m;
    // 初始化高度数组，用于记录每列的填充高度
    int *h = (int *)calloc(n, sizeof(int));
    // 调用回溯函数开始搜索
    dfs(h, n, m, 0);
    free(h);
    return ans;
}

int main() {
    int n = 2, m = 3;
    printf("%d\n", tilingRectangle(n, m));
    return 0;
}

四、代码解释

1. 全局变量 ans

用于存储贴满矩形所需的最小正方形数量。初始时，我们将其设为一个较大的值（这里设为 m），在回溯过程中不断更新这个值。

2. dfs 函数

这是回溯函数，它接受四个参数：

• h：一个数组，用于记录每列的填充高度。
• n：长方形的列数。
• m：长方形的行数。
• squares：当前已经使用的正方形数量。

在函数内部，首先检查当前使用的正方形数量是否已经超过了 ans，如果是则直接返回。然后检查是否所有列都已经被填满，如果是则更新 ans。接着找到当前高度最小的列，尝试从最大可能的边长开始放置正方形，检查是否可以放置，如果可以则更新高度数组并递归调用 dfs 函数。

3. tilingRectangle 函数

这是主函数，它接受两个参数 n 和 m，表示长方形的大小。首先处理特殊情况，如果 n 等于 m，则直接返回 1。然后保证 n 小于等于 m，减少搜索空间。接着初始化 ans 为 m，创建高度数组 h 并初始化为 0，调用 dfs 函数开始回溯搜索，最后释放 h 数组占用的内存并返回 ans。

4. main 函数

在 main 函数中，我们定义了一个示例输入 n = 2，m = 3，调用 tilingRectangle 函数计算结果并输出。

五、复杂度分析

• 时间复杂度：由于使用了回溯法，最坏情况下需要尝试所有可能的正方形放置方式，时间复杂度为 。
• 空间复杂度：主要是递归调用栈的空间和动态分配数组的空间，空间复杂度为O(n)。

六、总结

通过回溯法，我们可以解决用整数边正方形贴满长方形的最小数量问题。虽然这种方法在最坏情况下的时间复杂度较高，但对于较小的输入规模是可行的。在实际应用中，我们可以根据具体情况对算法进行优化，以提高效率。

希望这篇博客能帮助你理解如何使用 C 语言解决这个有趣的问题！如果你有任何疑问或建议，欢迎留言讨论。