• 解法 \(1\): 定義に従って順にカーペットを構成する

\(k=0,1,\ldots,N\) について、レベル \(i\) のカーペットに対応する文字列を順に構成していくことを考えます。
また、以下では、レベル \(k\) のカーペットに対応する \(S_i\) の \(j\) 文字目を \(S^k_{i,j}\) \((1\leq i,j\leq 3^k)\) で表します。

レベル \(0\) のカーペットは \(S^0_{0,0}=\)# とすればよいです。
\(k\geq 0\) についてレベル \((k+1)\) のカーペットを構成するためには定義より \(0\) 以上 \(2\) 以下の整数の組 \((x,y)\) それぞれについて次のようにすれば良いです。

• \((x,y)\neq (1,1)\) のとき、\(1\leq i,j\leq 3^k\) に対して、\(S^{k+1}_{x\cdot 3^k+i,y\cdot 3^k+j}=S^k_{i,j}\) とする。
• \((x,y)=(1,1)\) のとき、\(1\leq i,j\leq 3^k\) に対して、\(S^{k+1}_{x\cdot 3^k+i,y\cdot 3^k+j}=\). とする。

このようにして、レベル \(k\) のカーペットを構成することができます。計算量は \(O(3^{2N})\) であり、十分高速です。

よって、この問題を解くことができました。

• 解法 \(2\): カーペットのマスの色が白となる条件を整理する。

問題の条件を整理すると、レベル \(N\) のカーペットについて、上から \(i\) 行目かつ左から \(j\) 列目のマスが白色となる必要十分条件は、
\(1\leq k\leq N\) をみたすいずれかの整数 \(k\) について、 \((i-1)\) を \(3\) 進法で表した時の\(k\) 桁目と \((j-1)\) を \(3\) 進法で表した時の\(k\) 桁目がともに \(1\) になることであるとわかります。
そのため、各 \(1\leq i,j\leq 3^N\) についてその判定を行えば良いです。 計算量は \(O(N\cdot 3^{2N})\) であり、十分高速です。

c++ による実装例:

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n,l=1;
    char a[729][730];
    for(int i=0;i<729;i++)for(int j=0;j<730;j++)a[i][j]=0;

    cin>>n;
    a[0][0]='#';
    for(int k=0;k<n;k++){
        for(int x=0;x<3;x++){
            for(int y=0;y<3;y++){
                if((x==0)&&(y==0))continue;
                if((x==1)&&(y==1)){
                    for(int i=0;i<l;i++)for(int j=0;j<l;j++)a[x*l+i][y*l+j]='.';
                }
                else{
                    for(int i=0;i<l;i++){
                        for(int j=0;j<l;j++){
                            a[x*l+i][y*l+j]=a[i][j];
                        }
                    }
                }
            }
        }
        l*=3;
    }

    for(int i=0;i<l;i++)cout<<a[i]<<endl;

    return 0;
}