洛谷 P5461 赦免战俘

传送门

思路

洛谷7月月赛第一题

着实是一道大水题，然后我月赛的时候没做出来......

就是一道大模拟题呀，直接dfs就好了，我是反着处理的，所以最后要输出\(1-a[i][j]\)

#include <bits/stdc++.h>
#define N 1 << 10
using namespace std;

int a[N][N], n;

void solve(int x, int y, int l) { //x、y表示起点的横纵左边，l表示长度
    if(a[x][y]) return;//sd的剪枝？
    for(int i = x; i <= x + l - 1; i++) {
        for(int j = y; j <= y + l - 1; j++) {
            a[i][j] = 1;
        }
    }
    if(l == 1) return;//边界条件
    //递归其他三个区间
    solve(x + l, y, l >> 1);
    solve(x, y + l, l >> 1);
    solve(x + l, y + l, l >> 1);
}

int main() {
    scanf("%d", &n);
    int p = 1 << n;
    solve(1, 1, p / 2);
    for(int i = 1; i <= p; i++) {
        for(int j = 1; j <= p; j++) {
            cout << 1 - a[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}