上海计算机学会2026年1月月赛C++丙组T4 分形十字

分形十字

内存限制: 256 Mb
时间限制: 1000 ms

题目描述

给定一个整数 N，请打印出一个级别为 N 的分形十字，分形十字定义如下：
0 级分形十字是：

+

1 级分形十字是：

.+.
+++
.+.

2 级分形十字是：

….+….
…+++…
….+….
.+..+..+.
+++++++++
.+..+..+.
….+….
…+++…
….+….

总结来说，当 k>0 时，k 级分形十字是将五个 k−1 级的分形十字摆放在上、下、左、右、中，而四角用 . 填充成一个更大的十字。

输入格式

单个整数：表示N

输出格式

一个分形十字图案（由 + 和 . 组成的多行字符串）

数据范围

0≤N≤7

样例数据

输入：

1

输出：

.+.
+++
.+.

分形十字 题解（C++实现）

基于给定的C++代码，以下是分形十字题解的核心逻辑与执行流程解析（保留原代码逻辑，不做修改）。

整体设计思想

代码采用递归（DFS）+ 数组填充的方式实现分形十字，核心逻辑如下：

• 分形十字的边长为 $3^N$（N为级别），因此先计算出总边长 $m=3^N$；
• 用全局二维字符数组存储图案（数组大小2200×2200，足够覆盖N≤7的场景，因为 $3^7=2187$）；
• 递归函数 dfs 负责填充十字的关键位置：先填充中心的子十字，再将中心内容复制到上、下、左、右四个方向，同时将四角填充为.。

#include <bits/stdc++.h>
using namespace std;

// 全局二维字符数组，存储分形十字图案
// 大小2200×2200：因题目N≤7，3^7=2187，2200足够容纳且避免越界
char a[2200][2200];

/**
* 递归填充分形十字的DFS函数
* @param s 当前子区域的左上角起始坐标（1-based索引）
* @param x 当前子区域的边长
*/
void dfs(int s, int x) {
// 递归终止条件：x=1对应0级分形十字（仅单个'+'）
if (x == 1) {
// 在当前子区域的中心位置（s,s）放置'+'
a[s][s] = '+';
return;
}
// 将当前边长除以3，得到下一级子区域的边长
x /= 3;
// 递归填充当前区域中心的k-1级分形十字
// s+x是中心子区域的左上角坐标（原区域起始+子边长）
dfs(s + x, x);

// 遍历中心子区域的所有位置，将内容复制到上、下、左、右四个方向
// 中心子区域范围：行[i]从s+x到s+x+x-1，列[j]同理
for (int i = s + x; i < s + x + x; i++) {
for (int j = s + x; j < s + x + x; j++) {
// 向上复制：当前行向上偏移x行
a[i – x][j] = a[i][j];
// 向下复制：当前行向下偏移x行
a[i + x][j] = a[i][j];
// 向左复制：当前列向左偏移x列
a[i][j – x] = a[i][j];
// 向右复制：当前列向右偏移x列
a[i][j + x] = a[i][j];

// 填充四角为'.'（保证分形十字的四角无'+'）
a[i – x][j – x] = '.'; // 上左角
a[i + x][j – x] = '.'; // 下左角
a[i – x][j + x] = '.'; // 上右角
a[i + x][j + x] = '.'; // 下右角
}
}
}

int main() {
// 读取输入的分形级别N
int n;
cin >> n;

// 计算分形十字的总边长：3^n（0级1，1级3，2级9…）
int m = 1;
for (int i = 1; i <= n; i++) {
m *= 3;
}

// 调用DFS函数，从整个图案的左上角(1,1)开始填充n级分形十字
dfs(1, m);

// 遍历二维数组，逐行打印分形十字图案
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
cout << a[i][j];
}
// 每行打印完后换行
cout << "\\n";
}

return 0;
}

关键变量与函数解析

1. 全局数组 a[2200][2200]

• 作用：存储分形十字的每个位置字符，初始时数组值为随机值，但递归过程中会覆盖为+或.；
• 大小：2200×2200，满足题目中N≤7的最大边长（2187）需求，避免数组越界。

2. 递归函数 dfs(int s, int x)

• 参数说明：
  • s：当前子区域的左上角起始坐标（代码采用1-based索引，即从1开始计数）；
  • x：当前子区域的边长。
• 执行逻辑：
• 终止条件（0级十字）：当 x==1 时，在当前子区域的中心（即坐标(s,s)）放置+，直接返回；
• 递归分解：将当前边长 x 除以3，得到下一级子区域的边长（记为新的x）；
• 填充中心子十字：调用 dfs(s+x, x)，填充当前区域中心的k-1级十字；
• 复制中心内容到四向：遍历中心子区域的所有位置，将每个位置的字符复制到：
  • 上方：a[i-x][j] = a[i][j]（i-x为当前行向上偏移x行）；
  • 下方：a[i+x][j] = a[i][j]（i+x为当前行向下偏移x行）；
  • 左方：a[i][j-x] = a[i][j]（j-x为当前列向左偏移x列）；
  • 右方：a[i][j+x] = a[i][j]（j+x为当前列向右偏移x列）；
• 填充四角为.：将中心子区域四个对角的位置（上左、下左、上右、下右）设为.，保证四角无+。

3. 主函数 main()

• 步骤1：读取输入的级别n；
• 步骤2：计算总边长m：通过循环将1乘以3共n次，得到 $m=3^n$；
• 步骤3：调用 dfs(1, m)，从整个图案的左上角（坐标1,1）开始填充n级十字；
• 步骤4：双重循环遍历数组，逐行打印分形十字图案。

样例执行过程（输入n=1）

以输入1为例，拆解代码执行流程：

总结