LeetCode 1240. 铺瓷砖

2022-09-08 HGNULB 约 8 分钟

文章信息 7 个分类 1 个标签

分类

LeetCode CodeTop 困难未解决 2-5 阿里快手

题目描述

✅ 1240. 铺瓷砖

题意分析

用若干整数边长的正方形无重叠、无空隙地铺满 n × m 矩形，求最少块数。每块的边长都可以不同，当前能放的最大正方形不一定属于最优方案。

矩形边长最多为 13，可以回溯枚举铺法。把已经铺好的区域压缩成每列的填充高度，既能确定下一块的可放位置，也能合并重复状态。

解法：轮廓线回溯 + 记忆化

核心思路

[!blue]

令较短的边为列数 width，较长的边为高度 height。heights[col] 表示该列从底部连续填满的高度，下面没有空洞；used 表示已用瓷砖数。初始各列为零，所有列都达到 height 时才算铺满。

每次找高度最低且最靠左的列 start，设最低高度为 minHeight。这个空位下方已经填满，左边若有列，其高度又严格更高，所以覆盖这个空位的下一块正方形不能向下或向左延伸，它的左下角只能放在这里。

该正方形向右覆盖的各列必须都等于 minHeight：更高会重叠，更低则不存在，因为这里已经是全局最低高度。因此最大边长同时受连续等高列数、右侧剩余宽度和上方剩余高度限制。枚举从最大边长到 1 的所有选择，就枚举了覆盖这个必填空位的所有可能，不会漏掉完整铺法。

放入边长为 size 的正方形时，把对应 size 列的高度都增加 size，递归后再减回去。优先尝试大块只是为了尽早得到较小的答案上界，其他边长仍然必须搜索。

best 初始为全部使用单位正方形的块数。若 used >= best，继续放只会更多，可以剪枝。相同轮廓对应完全相同的剩余区域，若此前已经用更少或相同块数到达过，本次也不可能更优；所以 seen 记录最少已用块数，而不是只记录是否见过。

轮廓按 height + 1 进制编码，每列高度都在 0 到 height 之间，固定列数下不会冲突。题目中两边都不超过 13，编码可以存入 64 位整数。

解题步骤

两边相等时直接返回 1；否则统一矩形方向，初始化空轮廓、上界 best = n * m 和记忆表。

DFS 先执行已用块数剪枝和相同轮廓剪枝，再记录当前到达成本。

扫描轮廓，找到最左的最低列；若最低高度已经等于矩形高度，说明全部铺满，用 used 更新答案。

求当前位置最大可放边长，从大到小枚举；修改覆盖列、递归 used + 1，随后完整恢复这些列。

代码实现

class Solution {
    private int width;
    private int height;
    private int best;
    private Map<Long, Integer> seen;

    public int tilingRectangle(int n, int m) {
        if (n == m) {
            return 1;
        }

        width = Math.min(n, m);
        height = Math.max(n, m);
        best = n * m;
        seen = new HashMap<>();

        dfs(new int[width], 0);

        return best;
    }

    private void dfs(int[] heights, int used) {
        if (used >= best) {
            return;
        }

        long state = encode(heights);
        Integer oldUsed = seen.get(state);

        // 同一轮廓以更少或相同块数到过，本次无需再展开。
        if (oldUsed != null && oldUsed <= used) {
            return;
        }

        seen.put(state, used);

        int minHeight = height;
        int start = 0;

        for (int col = 0; col < width; col++) {
            // 只在严格更低时替换，保留最左的最低列。
            if (heights[col] < minHeight) {
                minHeight = heights[col];
                start = col;
            }
        }

        if (minHeight == height) {
            best = used;

            return;
        }

        int maxSize = getMaxSize(heights, start, minHeight);

        // 优先尝试大块以尽早得到较好上界，但仍要枚举其他边长。
        for (int size = maxSize; size >= 1; size--) {

            for (int col = start; col < start + size; col++) {
                heights[col] += size;
            }

            dfs(heights, used + 1);

            for (int col = start; col < start + size; col++) {
                // 恢复本次放置的每一列，避免影响下一种边长。
                heights[col] -= size;
            }
        }
    }

    private int getMaxSize(int[] heights, int start, int minHeight) {
        int maxSize = Math.min(width - start, height - minHeight);

        for (int size = 1; size <= maxSize; size++) {
            // 覆盖的各列必须等高，否则正方形会与已有区域重叠。
            if (heights[start + size - 1] != minHeight) {
                return size - 1;
            }
        }

        return maxSize;
    }

    private long encode(int[] heights) {
        long state = 0;
        long base = height + 1L;

        for (int value : heights) {
            state = state * base + value;
        }

        return state;
    }
}

func tilingRectangle(n int, m int) int {
    if n == m {
        return 1
    }

    width := n
    height := m
    if width > height {
        width, height = height, width
    }

    best := n * m
    heights := make([]int, width)
    seen := make(map[int64]int)

    var encode func() int64
    encode = func() int64 {
        state := int64(0)
        base := int64(height + 1)
        for _, value := range heights {
            state = state*base + int64(value)
        }
        return state
    }

    var getMaxSize func(start int, minHeight int) int
    getMaxSize = func(start int, minHeight int) int {
        maxSize := width - start
        if height-minHeight < maxSize {
            maxSize = height - minHeight
        }
        for size := 1; size <= maxSize; size++ {
            // 覆盖的各列必须等高，否则正方形会与已有区域重叠。
            if heights[start+size-1] != minHeight {
                return size - 1
            }
        }
        return maxSize
    }

    var dfs func(used int)
    dfs = func(used int) {
        if used >= best {
            return
        }

        state := encode()
        // 同一轮廓以更少或相同块数到过，本次无需再展开。
        if oldUsed, ok := seen[state]; ok && oldUsed <= used {
            return
        }
        seen[state] = used

        minHeight := height
        start := 0
        for col := 0; col < width; col++ {
            // 只在严格更低时替换，保留最左的最低列。
            if heights[col] < minHeight {
                minHeight = heights[col]
                start = col
            }
        }

        if minHeight == height {
            best = used
            return
        }

        maxSize := getMaxSize(start, minHeight)
        // 优先尝试大块以尽早得到较好上界，但仍要枚举其他边长。
        for size := maxSize; size >= 1; size-- {

            for col := start; col < start+size; col++ {
                heights[col] += size
            }

            dfs(used + 1)

            for col := start; col < start+size; col++ {
                // 恢复本次放置的每一列，避免影响下一种边长。
                heights[col] -= size
            }
        }
    }

    dfs(0)
    return best
}

复杂度分析

时间复杂度：搜索时间可按 $O(Vw^2)$ 估算，V 为实际展开次数、w 为轮廓宽度；同一轮廓以更低成本到达时可能再次展开。

空间复杂度：$O(S+nm+w)$，S 为记忆表中的轮廓数，含编码记录、轮廓与搜索栈。

关键点总结

[!green]

编码基数为高度加一，涵盖零到满高所有取值。

当前向右放置的实现必须选择最左最低列。

易错点总结

[!yellow]

只记轮廓是否见过，会阻止后来更省块数的路径。

不检查覆盖列等高，会与原有砖块重叠。

恢复范围与放置范围不同，会污染兄弟分支。

相似题目

题目	难度	关联与区别
790. 多米诺和托米诺平铺	中等	同样可用已填前沿状态描述铺放，本题正方形尺寸可变且求最少块数，原题固定骨牌形状并计数。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/58546309

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！