赦免战俘

题意

有一个 2^n * 2^n 的方阵。每次把当前方阵分成四个等大的小方阵，左上角小方阵全部赦免，剩下三个小方阵继续递归执行同样操作。输出最终矩阵，0 表示赦免，1 表示未赦免。

思路

先把整个矩阵初始化为 1。定义递归函数：

python

1pardon(top, left, size)

表示处理左上角为 (top, left)、边长为 size 的子方阵。

如果 size == 1，无法继续划分，直接返回。否则令 half = size // 2：

把当前区域左上 half * half 的格子改成 0；
对右上、左下、右下三个子方阵递归处理。

这题递归过程本身就是正解，不创建 brute.py。

Python 知识

/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：二维列表应使用列表推导式逐行创建，避免浅拷贝问题。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：print(*row) 可以按空格输出一行数字。
2 ** n 表示 $2^n$ 。
递归函数参数保存当前子问题的位置和规模。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23def pardon(top, left, size):
    if size == 1:
        return

    half = size // 2

    for row in range(top, top + half):
        for col in range(left, left + half):
            grid[row][col] = 0

    pardon(top, left + half, half)
    pardon(top + half, left, half)
    pardon(top + half, left + half, half)


n = int(input())
size = 2 ** n
grid = [[1 for _ in range(size)] for _ in range(size)]

pardon(0, 0, size)

for row in grid:
    print(*row)

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/**
 * 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 a[1030][1030]; // 赦免矩阵，1 表示未被赦免，0 表示赦免
int n;

// 递归处理左上角为 (x,y)、边长为 size 的方阵
void pardon(int x, int y, int size) {
    if (size == 1) return; // 最小单元，直接返回
    int half = size / 2;
    // 左上角 half*half 区域全部赦免（设为 0）
    for (int i = x; i < x + half; i++)
        for (int j = y; j < y + half; j++)
            a[i][j] = 0;
    // 递归处理其他三个子方阵
    pardon(x, y + half, half);       // 右上
    pardon(x + half, y, half);       // 左下
    pardon(x + half, y + half, half); // 右下
}

int main() {
    cin >> n;
    int size = 1 << n; // 2^n
    // 初始全为 1（未被赦免）
    for (int i = 1; i <= size; i++)
        for (int j = 1; j <= size; j++)
            a[i][j] = 1;
    // 从整个方阵开始递归处理
    pardon(1, 1, size);
    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++)
            cout << a[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

复杂度

矩阵大小为 S = 2^n。每个格子最多被赋值一次为 0，输出也需要处理 S^2 个格子，时间复杂度是 $O(S^2)$ ，空间复杂度是 $O(S^2)$ 。

总结

递归矩阵题要把“当前处理哪一块”写进函数参数。初始化全 1，再递归覆盖左上块为 0，能直接对应题意。

目录

题意

思路

Python 知识

代码

复杂度

总结