地毯填补问题

题意

给定一个 2^k x 2^k 棋盘，其中有一个特殊格不能覆盖。要求用 L 形地毯覆盖其余所有格子，并输出每块地毯的位置和形状。

思路

经典分治铺棋盘。

把当前棋盘分成四个象限。特殊格一定在其中一个象限。我们在棋盘中心放一块 L 形地毯，覆盖另外三个象限靠近中心的格子。这样做以后：

原来有特殊格的象限继续用原特殊格；
另外三个象限把刚刚被中心地毯覆盖的格子看作“特殊格”。

于是一个大问题变成四个规模减半的小问题。

Python 知识

递归函数 cover(top, left, size, special_x, special_y) 用左上角和边长描述子棋盘。
输出行先放进 answers，最后用 "\n".join(...) 一次输出。
1 << k 可以快速得到 2^k。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41def cover(top, left, size, special_x, special_y):
    if size == 1:
        return

    half = size // 2
    mid_x = top + half - 1
    mid_y = left + half - 1

    if special_x <= mid_x and special_y <= mid_y:
        answers.append((mid_x + 1, mid_y + 1, 1))
        cover(top, left, half, special_x, special_y)
        cover(top, left + half, half, mid_x, mid_y + 1)
        cover(top + half, left, half, mid_x + 1, mid_y)
        cover(top + half, left + half, half, mid_x + 1, mid_y + 1)
    elif special_x <= mid_x and special_y > mid_y:
        answers.append((mid_x + 1, mid_y, 2))
        cover(top, left, half, mid_x, mid_y)
        cover(top, left + half, half, special_x, special_y)
        cover(top + half, left, half, mid_x + 1, mid_y)
        cover(top + half, left + half, half, mid_x + 1, mid_y + 1)
    elif special_x > mid_x and special_y <= mid_y:
        answers.append((mid_x, mid_y + 1, 3))
        cover(top, left, half, mid_x, mid_y)
        cover(top, left + half, half, mid_x, mid_y + 1)
        cover(top + half, left, half, special_x, special_y)
        cover(top + half, left + half, half, mid_x + 1, mid_y + 1)
    else:
        answers.append((mid_x, mid_y, 4))
        cover(top, left, half, mid_x, mid_y)
        cover(top, left + half, half, mid_x, mid_y + 1)
        cover(top + half, left, half, mid_x + 1, mid_y)
        cover(top + half, left + half, half, special_x, special_y)


k = int(input())
x, y = map(int, input().split())

answers = []
cover(1, 1, 1 << k, x, y)

print("\n".join(f"{row} {col} {shape}" for row, col, shape in answers))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int k, sz, cnt;
int ans[10000][3];

void cover(int top, int left, int size, int sx, int sy) {
    if (size == 1) return;
    int half = size / 2;
    int mx = top + half - 1, my = left + half - 1;
    if (sx <= mx && sy <= my) {
        ans[cnt][0] = mx + 1; ans[cnt][1] = my + 1; ans[cnt][2] = 1; cnt++;
        cover(top, left, half, sx, sy);
        cover(top, left + half, half, mx, my + 1);
        cover(top + half, left, half, mx + 1, my);
        cover(top + half, left + half, half, mx + 1, my + 1);
    } else if (sx <= mx && sy > my) {
        ans[cnt][0] = mx + 1; ans[cnt][1] = my; ans[cnt][2] = 2; cnt++;
        cover(top, left, half, mx, my);
        cover(top, left + half, half, sx, sy);
        cover(top + half, left, half, mx + 1, my);
        cover(top + half, left + half, half, mx + 1, my + 1);
    } else if (sx > mx && sy <= my) {
        ans[cnt][0] = mx; ans[cnt][1] = my + 1; ans[cnt][2] = 3; cnt++;
        cover(top, left, half, mx, my);
        cover(top, left + half, half, mx, my + 1);
        cover(top + half, left, half, sx, sy);
        cover(top + half, left + half, half, mx + 1, my + 1);
    } else {
        ans[cnt][0] = mx; ans[cnt][1] = my; ans[cnt][2] = 4; cnt++;
        cover(top, left, half, mx, my);
        cover(top, left + half, half, mx, my + 1);
        cover(top + half, left, half, mx + 1, my);
        cover(top + half, left + half, half, sx, sy);
    }
}

int main() {
    int x, y;
    cin >> k >> x >> y;
    sz = 1 << k;
    cover(1, 1, sz, x, y);
    for (int i = 0; i < cnt; i++)
        cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << endl;
    return 0;
}

复杂度

每块地毯输出一次，地毯数量为 $(4^k-1)/3$ 。时间复杂度和输出规模同阶，空间复杂度主要是递归栈与输出列表。

总结

这题的关键是“中心补一块”，让四个子棋盘都变成同一种问题。

目录

题意

思路

Python 知识

代码

复杂度

总结