上海计算机学会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：当前子区域的边长。
• 执行逻辑：
  1. 终止条件（0级十字）：当x==1时，在当前子区域的中心（即坐标(s,s)）放置+，直接返回；
  2. 递归分解：将当前边长x除以3，得到下一级子区域的边长（记为新的x）；
  3. 填充中心子十字：调用dfs(s+x, x)，填充当前区域中心的k-1级十字；
  4. 复制中心内容到四向：遍历中心子区域的所有位置，将每个位置的字符复制到：
     • 上方：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列）；
  5. 填充四角为.：将中心子区域四个对角的位置（上左、下左、上右、下右）设为.，保证四角无+。

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为例，拆解代码执行流程：

1. main函数中，n=1，计算m=3（1×3）；
2. 调用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]='.'；
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级十字，再复制到四向，四角填充.；
2. 坐标采用1-based索引，递归函数的s是子区域起始坐标，x是子区域边长；
3. 数组大小2200×2200适配N≤7的最大边长，避免越界，递归终止条件对应0级十字的单个+。