跳到主要内容

铺砖问题（12 / 22 填满 r*c 空间）

顺丰科技笔试编程题 · ACM 模式（stdin/stdout，多组数据）

题目描述​

有一块 r × c 的矩形空间，现在有两种方块：

  • 1 × 2（可横放或竖放，覆盖 2 个格子）；
  • 2 × 2（覆盖 4 个格子）。

要求用这两种方块把空间完全填满（不能重叠、不能留空、不能超出边界）。

请判断该空间能否被填满：

  • 若能填满，输出 Y 和最少需要多少块方块；
  • 若不能填满，输出 N 和 -1。

输入格式​

  • 第 1 行：整数 t，表示 t 组数据；
  • 接下来 t 行：每行两个整数 r c，表示空间的行数和列数。

输出格式​

  • 每组数据输出两行：
    • 第 1 行：Y 或 N（是否能填满）；
    • 第 2 行：最少需要的方块数；若不能填满则输出 -1。

示例​

示例 1​

输入：

3
2 3
1 3
2 2

输出：

Y
2
N
-1
Y
1

说明：

  • 2×3：可填满，最少 2 块（1 块 2×2 + 1 块 1×2）；
  • 1×3：面积 3 是奇数，无法填满；
  • 2×2：1 块 2×2 即可。

示例 2​

输入：

4
1 2
3 4
1 1
6 5

输出：

Y
1
Y
4
N
-1
Y
9

说明：

  • 6×5：最少 9 块（6 块 2×2 + 3 块竖放的 1×2）。

解题思路​

第一步：理解问题本质​

两类方块覆盖的格子数分别为 2 和 4，都是偶数。因此：

整个空间的总格子数 r*c 必须是偶数，否则任何方案都无法填满。

这是第一个判断条件：r*c 为奇数 → 直接输出 N 和 -1。

当 r*c 为偶数时，填满一定可行（构造方法见后文），问题变成：求最少方块数。

要减少方块总数，就要尽量多用"覆盖面积更大"的 2×2 方块（一块顶两块 1×2）。于是问题转化为：在不破坏"剩余区域能用 1×2 填满"的前提下，最多能放多少个 2×2 方块。

第二步：暴力解法（DFS 回溯）​

思路： 逐格尝试所有放法。从第一个未覆盖的格子出发，枚举放 2×2、横放 1×2、竖放 1×2 三种选择，递归搜索，取块数最少的方案。

def min_blocks(r, c):
    grid = [[False] * c for _ in range(r)]
    best = [float("inf")]

    def dfs(cnt):
        # 找第一个未覆盖格子
        ...
        # 尝试三种放法（2x2 / 横1x2 / 竖1x2）
        ...

    if r * c % 2 == 1:
        return None
    dfs(0)
    return best[0]

为什么不够好：

  • 每块方块有 3 种放法、位置可任意，复杂度接近指数级；
  • r、c 稍大（如 30 甚至更大）就完全无法运行；
  • 题目只要求判断可行性 + 最少数，存在完全不需要搜索的规律。

第三步：找规律 —— "偶数维成带"构造​

不妨假设 r 是偶数（c 是奇数），把空间按每 2 行一组切成 r/2 个"横带"：

  • 每个横带是 2 × c，可以放 (c-1)/2 个 2×2 方块，还剩 2 × 1 的空位；
  • 剩余的空位用 1 块竖放的 1×2 方块补齐（横放也可以，效果一样）。
r=4, c=5 的填法（4 块 2×2 + 2 块竖 1×2 = 6 块）：

带1: [2x2][2x2][竖]   → 2 块 2×2 + 1 块 1×2
带2: [2x2][2x2][竖]   → 2 块 2×2 + 1 块 1×2

总块数 = r/2 个横带 × ceil(c/2) 块/带。

当 c 也是偶数时，每个横带刚好 c/2 个 2×2，公式退化为 (r/2) × (c/2)。

若 r 是奇数而 c 是偶数（此时 r*c 才可能为偶数），对称地按每 2 列一组，结论相同。

第四步：最优解法（O(1) 公式）​

可行性： r*c 为偶数。

最少块数：

若 r 为偶数：最少块数 = (r/2) × ceil(c/2)
若 c 为偶数：最少块数 = (c/2) × ceil(r/2)

为什么已经最优：

  • 每块 2×2 覆盖 4 格，而一个 2 行的横带最多容纳 floor(c/2) 个 2×2；
  • 全图最多能放的 2×2 数量被每个横带的上限锁定，构造方案正好达到该上限；
  • 剩下的格子用 1×2 补齐，块数不会再少（用穷举验证小规模 r,c ≤ 7 与公式完全一致）。

完整代码实现​

算法可视化 · 逐帧回放这道题的代码13 帧 · 录制输入

写法一（主）：逐行读取 sys.stdin.readline​

每行一个测试用例，读一行处理一行，可读性最好。

import sys

def min_blocks(r, c):
    """返回 (是否可填满, 最少方块数)；不可填满时返回 (False, -1)"""
    if (r * c) % 2 == 1:
        return False, -1

    if r % 2 == 0:
        # 以 r 为偶数维，按 2 行一组铺 2×2，剩余一列用竖放 1×2 补齐
        return True, (r // 2) * ((c + 1) // 2)
    else:
        # r 为奇数则 c 必为偶数，以 c 为偶数维
        return True, (c // 2) * ((r + 1) // 2)

def solve():
    input = sys.stdin.readline     # 必须写在 solve() 内部，便于测试时替换 sys.stdin

    first = input()
    if not first:                  # 空输入直接结束
        return
    t = int(first)

    out = []
    for _ in range(t):
        r, c = map(int, input().split())
        ok, blocks = min_blocks(r, c)
        out.append("Y" if ok else "N")
        out.append(str(blocks))

    sys.stdout.write("\n".join(out) + "\n")

if __name__ == "__main__":
    solve()

写法二（备选）：一次性读取全部 token sys.stdin.buffer.read()​

用 read() 一次读完再按 token 取用：速度快、不关心输入分布在几行。 StringIO 没有 .buffer，本地测试需用 sys.stdin.read().encode() 兜底。

（min_blocks 与写法一完全相同，这里再写一遍是为了让这段能独立运行。）

import sys

def _read_input():
    """读取全部输入（兼容真实评测 stdin 与本地 StringIO 测试）"""
    try:
        return sys.stdin.buffer.read()
    except AttributeError:
        return sys.stdin.read().encode()

def min_blocks(r, c):
    """返回 (是否可填满, 最少方块数)；不可填满时返回 (False, -1)"""
    if (r * c) % 2 == 1:
        return False, -1

    if r % 2 == 0:
        # 以 r 为偶数维，按 2 行一组铺 2×2，剩余一列用竖放 1×2 补齐
        return True, (r // 2) * ((c + 1) // 2)
    else:
        # r 为奇数则 c 必为偶数，以 c 为偶数维
        return True, (c // 2) * ((r + 1) // 2)

def solve():
    data = _read_input().split()
    if not data:
        return
    it = iter(data)
    t = int(next(it))

    out = []
    for _ in range(t):
        r = int(next(it))
        c = int(next(it))
        ok, blocks = min_blocks(r, c)
        out.append("Y" if ok else "N")
        out.append(str(blocks))

    sys.stdout.write("\n".join(out) + "\n")

if __name__ == "__main__":
    solve()

两种写法效果完全等价，run_tests() 用 io.StringIO 替换 sys.stdin 后都能正常运行。 完整版（含 --test 自测与样例注释，写法二以注释保留）见 code-training/sf/sf_tiling_1x2_2x2.py。

示例推演​

以 r=6, c=5 为例，逐步计算：

第 1 步：判断可行性

r*c = 6*5 = 30，为偶数 → 可填满，输出 Y

第 2 步：计算最少块数

r=6 为偶数 → 最少块数 = (6//2) * ceil(5/2) = 3 * 3 = 9

第 3 步：构造验证

按 2 行一组，切出 3 个横带，每个横带放 2 个 2×2 和 1 个竖放 1×2：

带1: [2x2][2x2][竖]     → 2×2 方块 ×2 + 1×2 方块 ×1
带2: [2x2][2x2][竖]     → 2×2 方块 ×2 + 1×2 方块 ×1
带3: [2x2][2x2][竖]     → 2×2 方块 ×2 + 1×2 方块 ×1
  • 2×2 方块：3 带 × 2 = 6 块，覆盖 24 格；
  • 1×2 方块：3 带 × 1 = 3 块，覆盖 6 格；
  • 合计 9 块，覆盖 24 + 6 = 30 格，正好填满。

第 4 步：输出

Y
9

复杂度分析​

解法时间复杂度空间复杂度说明
暴力（DFS 回溯）指数级O(r×c)放法组合爆炸，仅适用于极小规模
最优（O(1) 公式）O(1)O(1)每组数据常数时间得出答案

易错点总结​

1. 忘记"面积必须为偶数"​

两类方块都覆盖偶数个格子，所以 r*c 为奇数时一定无解。这是最容易漏的判断。

2. 用 ceil(奇数/2) 时算错​

ceil(c/2) 在代码里等价于 (c + 1) // 2。例如 c=5 时 (5+1)//2 = 3，如果误写成 c//2 = 2，会少算一个横带里的补齐块。

3. 偶数维判断选错​

代码里用 r % 2 == 0 判断：若 r 是奇数，则 c 必为偶数（否则面积是奇数早已排除），此时用 c 当偶数维。两维都是偶数时，两个公式结果相同。

4. 输出格式​

每组数据要输出两行（先 Y/N，再数字/-1），中间换行，最后一组后也要换行。

5. 认为"面积是偶数就一定能用 2×2 填满"​

例如 2×1 面积 2 是偶数，但放不下任何 2×2，只能用 1×2。公式里的 ceil 正是为这种"奇数列"场景兜底。

扩展思考​

  • 只用 1×2 铺满的方案数： 这是经典 POJ 2411 Mondriaan's Dream，用状态压缩 DP 计算方案数，与本题的"最少数"互补。
  • 只用 2×2（或正方形）的最小块数： 当 r×c 不是偶数倍时，需要更复杂的分割，类似 LeetCode 1240 铺瓷砖（用任意整数边正方形）。
  • 如果方块规格变成 1×k 与 k×k： 可行性条件推广为"面积能被 k 整除"……需要重新推导。
  • 穷举验证： 小规模（r,c ≤ 7）可用 DFS 回溯穷举，与公式对拍确认无误，是这类数学题的可靠自检方式。

相关题目​

自测​

加载评论中...