赦免战俘

洛谷·深入浅出 · 代码 · cpp · 难度 3/5 · 共 876 字

递归分治生成赦免矩阵（0 赦免 1 不赦免）

洛谷
例题

正文

// 原题：https://oj.yecheng.tv/p/1434
// 题意：2^n * 2^n 方阵，每次把左上角四分之一全部赦免（置 0），其余三个象限继续同样处理，输出 01 矩阵。
// 思路：递归函数把左上象限整块置 0，再对另外三个象限递归；递归到 1x1 结束。初始全 1。
// 复杂度：O(4^n)。
// 易错点：每次是“整块左上置 0”而不是只置一个；递归在三个非左上象限上进行。
#include <iostream>
using namespace std;
int a[1030][1030];
void solve(int x, int y, int s){
    if(s == 1) return;
    int h = s / 2;
    for(int i = x; i < x + h; i++)
        for(int j = y; j < y + h; j++) a[i][j] = 0;
    solve(x + h, y, h);
    solve(x, y + h, h);
    solve(x + h, y + h, h);
}
int main(){
    int n;
    cin >> n;
    int s = 1;
    for(int i = 0; i < n; i++) s *= 2;
    for(int i = 0; i < s; i++)
        for(int j = 0; j < s; j++) a[i][j] = 1;
    solve(0, 0, s);
    for(int i = 0; i < s; i++){
        for(int j = 0; j < s; j++){
            if(j) cout << " ";
            cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}

赦免战俘

正文

洛谷·深入浅出的其它内容