考点:

$(递归+坐标变换)$

思路做法:

首先由题意我们可以知道,每一个$n$级的盒子,都是由$5个n-1级的盒子构成的,如果所示:$

我们可以很容易发现这个问题是可以分解成子问题去做,即要求$B(n),则要先求出B(n-1)$,然后我们现在分析我们已知了$B(n-1)$如何通过坐标变换得到$B(n)$,首先我们可以从图中看出它是由左上角的$B(n-1)$往4个位置复制了一次构成的,分别是右上，中间,左下,右下。

现在我们来分析左上角的$B(n-1)和其它B(n-1)直接的位置关系$：
这里我们只需要分析$B(n-1)$最左上角的那个点如何通过平移变换到其余四个位置，就可以知道整个$B(n-1)的坐标变换$,从而求出$B(n)$。

在分析坐标变换之前，由题目和图我们可以知道对于一个$n$级盒子的大小是:$3^{n-1}*3^{n-1}$

现在我们来分析坐标变换：

由上面分析我们可以得到最终坐标变换的公式：

这里为了方便,我们用矩阵g[x][y]=1表示这个位置填'X',g[x][y]=0,表示这个位置是填" "
这里我们只处理g[x][y]=1,因为如果是0,就不用管，因为我们默认矩阵一开始全是0

若g[x][y]=1
对于n级盒子,它上一级盒子n-1级的大小是last*last;
g[x][y+2*last]=1;
g[x+last][y+last]=1;
g[x+2*last][y]=1;
g[x+2*last][y+2*last]=1;

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2200;
int g[N][N];

void dfs(int u)
{
    if(u==1){
        g[1][1]=1;
        return ;
    }
    //递归思想先把n-1级搞好
    dfs(u-1);
    //把u-1级的矩阵往4个方向复制
    int last=pow(3,u-2); //u-1级的盒子的边长
    for(int i=1;i<=last;i++){
        for(int j=1;j<=last;j++){
            //坐标变换
            if(!g[i][j])continue;
            g[i][j+2*last]=1;
            g[i+last][j+last]=1;
            g[i+2*last][j]=1;
            g[i+2*last][j+2*last]=1;
        }
    }
}

int main()
{
    dfs(7);
    int n;
    while(cin>>n,n!=-1)
    {
        int m=pow(3,n-1);
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                if(g[i][j])cout<<'X';
                else cout<<' ';
            }
            cout<<endl;
        }
        cout<<"-\n";
    }

    return 0;
}