P5461 【模板】赦免战俘——题解

解题思路

先把整个矩阵填成 1。递归处理一个正方形时，将它的左上四分之一全部改为 0，然后只递归处理右上、左下、右下三个四分之一。边长为 1 时停止。

正确性说明

每个递归节点严格执行题目规定：当前左上块全部赦免，其余三块继续同样规则。递归终止条件与“不能再分”一致，因此最终每个位置的状态与题目过程相同。

复杂度分析

设矩阵边长为 $L=2^n$。总写入和输出规模为 $O(L^2)$，递归深度 $O(n)$，矩阵空间 $O(L^2)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int a[1025][1025];
void dfs(int x,int y,int len){
    if(len==1) return;
    int h=len/2;
    for(int i=x;i<x+h;i++) for(int j=y;j<y+h;j++) a[i][j]=0;
    dfs(x+h,y,h); dfs(x,y+h,h); dfs(x+h,y+h,h);
}
int main(){
    int n;cin>>n;int len=1<<n;
    for(int i=0;i<len;i++)for(int j=0;j<len;j++)a[i][j]=1;
    dfs(0,0,len);
    for(int i=0;i<len;i++){for(int j=0;j<len;j++){if(j)cout<<' ';cout<<a[i][j];}cout<<'\n';}
    return 0;
}

#include <bits/stdc++.h> using namespace std; int a[1025][1025]; void dfs(int x,int y,int len){ if(len==1) return; int h=len/2; for(int i=x;i<x+h;i++) for(int j=y;j<y+h;j++) a[i][j]=0; dfs(x+h,y,h); dfs(x,y+h,h); dfs(x+h,y+h,h); } int main(){ int n;cin>>n;int len=1<<n; for(int i=0;i<len;i++)for(int j=0;j<len;j++)a[i][j]=1; dfs(0,0,len); for(int i=0;i<len;i++){for(int j=0;j<len;j++){if(j)cout<<' ';cout<<a[i][j];}cout<<'\n';} return 0; }