题解 P5461 【赦免战俘】

VenusM1nT · 2019-07-15 08:22:33 · 题解

模拟。

模拟赛打完吃完饭就 5:10 了……月赛只剩不到一个小时，所以码完 T1 就回酒店了……

那么这道题显然是一个简单的递归题，虽然这么做跑的比较慢，但是毕竟好写嘛。

做法就是将当前矩阵的左上一块标记上，然后递归进剩下三块继续做，如果当前矩阵为 1\times 1 直接退出递归即可。

#include<bits/stdc++.h>
#define MAXN 2005
#define reg register
#define inl inline
using namespace std;
int n;
bool ans[MAXN][MAXN];
void Dfs(reg int x,reg int y,reg int xx,reg int yy)
{
    if(x==xx && y==yy) return;
    reg int tx=(x+xx)/2,ty=(y+yy)/2;
    for(reg int i=x;i<=tx;i++)
    {
        for(reg int j=y;j<=ty;j++) ans[i][j]=1;
    }
    Dfs(x,ty+1,tx,yy);
    Dfs(tx+1,y,xx,ty);
    Dfs(tx+1,ty+1,xx,yy);
}
int main()
{
    reg int x;
    scanf("%d",&x);
    n=1<<x;
    Dfs(1,1,n,n);
    for(reg int i=1;i<=n;i++)
    {
        for(reg int j=1;j<=n;j++) printf("%d%c",ans[i][j]?0:1,j==n?'\n':' ');
    }
    return 0;
}