# 菜鸟的coding · Day 033
黑白格
题目
上课不许下五子棋！
小J和小R今天在下课时在手机上开始下五子棋，他们看着这个棋盘，陷入了沉思。
小J："这个棋盘黑白间隔太单调了，能不能来玩一点有意思的呀。"
小R："那我们来改变一下，给一个空棋盘上色，每一次我将棋盘分为四份，对其中的左上，右上，右下三个部分进行处理，划分结束后再一次将其分成四份，同样处理左上，右上，右下三个部分，直到只剩下了边长为2的方格时，为左上，右上，右下三个部分填入1。这样完成上色。"
小J："听起来有点意思，让我来试试。"
尝试的过程中小J发现好像有一点困难，想要请你一起来帮助他，现在到你动手了！
请根据小J和小R的目标，根据输入的棋盘边长完成上色，之后输出整个棋盘。
输入：第一行一个整数 N，表示棋盘边长。
输出：按照要求输出对应的棋盘样式。
样例1：
输入
2
输出
1 1 0 1
样例2：
输入
8
输出
1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1
提示：对于 60% 的数据，保证 N≤500。对于 100% 的数据，保证 N≤5000，N保证为2的方幂。
思路
递归构造：将 n×n 棋盘四等分，左上、右上、右下三块各复制 n/2 规模的子问题结果，左下始终保持0，直到 2×2 的基础块直接返回。
#include<bits/stdc++.h>
using namespace std;
// 返回一个n*n的棋盘
vector<vector<int>> build(int n) {
if (n == 2) { // 递归终点
return {
{1, 1},
{0, 1}
};
}
// 构造一个更小的棋盘
auto half = build(n / 2);
// 创建一个全0的棋盘
vector<vector<int>> res(n, vector<int>(n, 0));
// 遍历小棋盘，并复制到大棋盘左上右上右下
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < n / 2; j++) {
res[i][j] = half[i][j]; // 左上
res[i][j + n/2] = half[i][j]; // 右上
res[i + n/2][j + n/2] = half[i][j]; // 右下
// 左下默认0
}
}
return res;
}
int main() {
int n;
cin >> n;
auto ans = build(n);
for (auto &row : ans) {
for (int i = 0; i < n; i++) {
cout << row[i];
if (i != n - 1) cout << " ";
}
cout << "\n";
}
return 0;
}复杂度分析
- 时间复杂度：O(n²)，每个格子恰好被填写一次
- 空间复杂度：O(n²)，递归各层棋盘总大小为等比级数，收敛于 O(n²)
今日感受
本质是分形递归与结构复制，理解"构造规则"比公式更直观，逐层展开就不难。