真·数字方阵

观察样例可以发现，分割出的非右上角小方阵最后都会变成 1 0 1 1 的单位方阵，所以可以通过递归来操作，直到最后到达单位长度后就进行操作

参考代码（python）

from sys import stdin,setrecursionlimit
from math import inf,ceil,sqrt
from collections import Counter,deque

def dfs(x:int,y:int,p:int):
    if p==1:
        s[x+1][y-1]=1
        s[x+1][y]=1
        s[x][y-1]=1
        return
    dfs(x+(1<<(p-1)),y,p-1)
    dfs(x,y-(1<<(p-1)),p-1)
    dfs(x+(1<<(p-1)),y-(1<<(p-1)),p-1)


n=int(stdin.readline())
s=[[0 for _ in range(1<<n)]for i in range(1<<n)]
dfs(0,(1<<n)-1,n)
for i in s:
    print(' '.join(map(str,i)))

原题：P5461 赦免战俘 - 洛谷

递归题。我不相信有人能在赛场上手敲出1024*1024（n=10）的矩阵...

参考代码（C++）：

#include <bits/stdc++.h>
using namespace std;

int m[1030][1030];

void draw(int sx, int sy, int l) {
    if (l == 1) {
        m[sx][sy] = 1;
        return;
    }
    draw(sx, sy, l / 2);
    draw(sx + l / 2, sy, l / 2);
    draw(sx + l / 2, sy + l / 2, l / 2);
}

int main() {
    int n;
    cin >> n;
    int len = pow(2, n);
    draw(1, 1, len);
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= len; j++) {
            cout << m[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

分治递归： 用递归的方式实现分治策略

分治： 把一个大问题分解成若干个相似的子问题 分别解决后再合并结果

递归： 函数调用自身

#r是行 c是列 size是边长 grid是方形列表
#正方形会一直递归到被分割成一个单独的像素后才会停止
def fill_grid(r, c, size, grid):
    if size == 1:
        grid[r][c] = 1
        return
    half = size // 2
    #左上
    fill_grid(r,c,half,grid)
    #右下
    fill_grid(r+half,c+half,half,grid)
    #左下
    fill_grid(r+half,c,half,grid)

def main():
    n = int(input().strip())
    size = 2 ** n
    grid = [[0] * size for _ in range(size)]
    #先从左上角开始 是因为左上角可以只通过加法 到达左下 右下 
    fill_grid(0,0,size,grid)

    for i in range(size):
        #按行打印
        print(' '.join(map(str,grid[i])))
if __name__ == "__main__":
    main()