上海计算机学会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）+ 数组填充的方式实现分形十字，核心逻辑如下：
- 分形十字的边长为3N3^N3N（N为级别），因此先计算出总边长m=3Nm=3^Nm=3N；
- 用全局二维字符数组存储图案（数组大小2200×2200，足够覆盖N≤7的场景，因为37=21873^7=218737=2187）；
- 递归函数
dfs负责填充十字的关键位置：先填充中心的子十字，再将中心内容复制到上、下、左、右四个方向，同时将四角填充为.。
#include<bits/stdc++.h>usingnamespacestd;// 全局二维字符数组，存储分形十字图案// 大小2200×2200：因题目N≤7，3^7=2187，2200足够容纳且避免越界chara[2200][2200];/** * 递归填充分形十字的DFS函数 * @param s 当前子区域的左上角起始坐标（1-based索引） * @param x 当前子区域的边长 */voiddfs(ints,intx){// 递归终止条件：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(inti=s+x;i<s+x+x;i++){for(intj=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]='.';// 下右角}}}intmain(){// 读取输入的分形级别Nintn;cin>>n;// 计算分形十字的总边长：3^n（0级1，1级3，2级9...）intm=1;for(inti=1;i<=n;i++){m*=3;}// 调用DFS函数，从整个图案的左上角(1,1)开始填充n级分形十字dfs(1,m);// 遍历二维数组，逐行打印分形十字图案for(inti=1;i<=m;i++){for(intj=1;j<=m;j++){cout<<a[i][j];}// 每行打印完后换行cout<<"\n";}return0;}关键变量与函数解析
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列）；
- 上方：
- 填充四角为
.：将中心子区域四个对角的位置（上左、下左、上右、下右）设为.，保证四角无+。
- 终止条件（0级十字）：当
3. 主函数main()
- 步骤1：读取输入的级别
n； - 步骤2：计算总边长
m：通过循环将1乘以3共n次，得到m=3nm=3^nm=3n； - 步骤3：调用
dfs(1, m)，从整个图案的左上角（坐标1,1）开始填充n级十字； - 步骤4：双重循环遍历数组，逐行打印分形十字图案。
样例执行过程（输入n=1）
以输入1为例，拆解代码执行流程：
main函数中，n=1，计算m=3（1×3）；- 调用
dfs(1, 3)：x=3≠1，执行x/=3→x=1；- 调用
dfs(1+1, 1) = dfs(2,1)：x=1，触发终止条件，设置a[2][2]='+'，返回；
- 进入循环：
i从1+1=2到1+1+1-1=2（即i=2），j同理从2到2； - 执行循环内逻辑：
a[2-1][2] = a[2][2]→a[1][2]='+'（上方）；a[2+1][2] = a[2][2]→a[3][2]='+'（下方）；a[2][2-1] = a[2][2]→a[2][1]='+'（左方）；a[2][2+1] = a[2][2]→a[2][3]='+'（右方）；- 四角设为
.：a[1][1]='.'、a[3][1]='.'、a[1][3]='.'、a[3][3]='.'；
- 打印数组：
- 第1行：
a[1][1]a[1][2]a[1][3]→.+.； - 第2行：
a[2][1]a[2][2]a[2][3]→+++； - 第3行：
a[3][1]a[3][2]a[3][3]→.+.；
最终输出与样例一致。
- 第1行：
总结
- 代码核心是递归分解+中心复制：将k级十字分解为中心的k-1级十字，再复制到四向，四角填充
.； - 坐标采用1-based索引，递归函数的
s是子区域起始坐标，x是子区域边长； - 数组大小2200×2200适配N≤7的最大边长，避免越界，递归终止条件对应0级十字的单个
+。