题解：P5461 赦免战俘

2011hym · 2025-07-10 22:02:55 · 题解

前言

非常非常经典的递归题目，还是我第一个 A 掉的黄题。

当时我们机房还有人管它叫赤兔战俘。

解题思路

显然若将目标矩阵平分为 4 个小矩阵，左上角的人一定会被赤兔赦免。

注意递归的要素：

• 函数功能
• 结束条件
• 问题分解

那么套用到此题上呢？

函数功能

此函数的功能显然是判断矩阵中有谁会被赦免，这是很明确的目标。

结束条件

因为题目中给出的就是 2^n\times 2^n 的矩阵，这也保证了最后一定能被划分为多个 2\times 2 的矩阵。

故而终止条件就是划分到只剩下 2\times 2。

问题分解

更不用说了，直接对半分。

总体思路

在每次递归中：

• 如果当前边长为 2，直接将左上角的元素置为 0，然后结束。
• 否则，将当前矩阵分成四个子矩阵：
  • 左上角的子矩阵全部设为 0。
  • 左下、右下、右上的子矩阵依次递归调用函数。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,o=1,a[1145][1145];
void dfs(int x,int l,int q){//三个参数意思分别是边长，以左上角为坐标原点的行数与列数。
    if(x==2){
        a[l][q]=0;
        return;
    }
    for(int i=l;i<=l+x/2-1;i++){
        for(int j=q;j<=q+x/2-1;j++){
            a[i][j]=0;
        }
    }
    dfs(x/2,l+x/2,q);
    dfs(x/2,l+x/2,q+x/2);
    dfs(x/2,l,q+x/2);
}
int main(){
    ios::sync_with_stdio;
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        o*=2;
    }
    for(int i=1;i<=o;i++){
        for(int j=1;j<=o;j++){
            a[i][j]=1;
        }
    }
    dfs(o,1,1);
    for(int i=1;i<=o;i++){
        for(int j=1;j<=o-1;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<a[i][o]<<endl;
    }
    return 0;
}