【题目来源】
洛谷：P5461 赦免战俘 - 洛谷
【题目描述】
现有 \(2^n\times2^n(n\le10)\) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 \(4\) 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 \(3\) 个小矩阵中，每一个矩阵继续分为 \(4\) 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。
给出 \(n\)，请输出每名作弊者的命运，其中 \(0\) 代表被赦免，\(1\) 代表不被赦免。
【输入】
一个整数 \(n\)。
【输出】
\(2^n\times2^n(n\le10)\) 的 \(01\) 矩阵，代表每个人是否被赦免。数字之间有一个空格。
【输入样例】
3
【输出样例】
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
【算法标签】
《洛谷 P5461 赦免战俘》 #模拟# #递归# #洛谷月赛#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件（万能头文件）
using namespace std; // 使用标准命名空间int a[1100][1100]; // 定义二维数组：存储分形图案/*** 递归生成分形图案* @param x 当前区域左上角的x坐标* @param y 当前区域左上角的y坐标* @param z 当前区域的边长* @return 无返回值*/
int fzdg(int x, int y, int z)
{if (z == 1) // 基本情况：最小单元直接返回{return 0;}// 填充当前区域左上角的1/4区域for (int i = x; i < x + z / 2; i++) {for (int j = y; j < y + z / 2; j++) {a[i][j] = 1; // 标记为填充区域}}// 递归处理其他三个1/4区域fzdg(x + z / 2, y, z / 2); // 右上区域fzdg(x, y + z / 2, z / 2); // 左下区域fzdg(x + z / 2, y + z / 2, z / 2); // 右下区域
}int main()
{int n; // 定义变量：分形迭代次数int fz; // 定义变量：分形图案边长cin >> n; // 输入迭代次数fz = pow(2, n); // 计算分形图案边长（2的n次方）fzdg(1, 1, fz); // 从(1,1)开始生成分形图案// 输出分形图案（0表示填充，1表示空白）for (int i = 1; i <= fz; i++) {for (int j = 1; j <= fz; j++) {if (a[i][j] == 1) cout << "0 "; // 填充区域输出0else cout << "1 "; // 空白区域输出1}cout << endl; // 每行结束换行}return 0; // 程序正常结束
}
【运行结果】
3
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1