103572: [Atcoder]ABC357 C - Sierpinski carpet

Problem Statement

For a non-negative integer $K$, we define a level-$K$ carpet as follows:

• A level-$0$ carpet is a $1 \times 1$ grid consisting of a single black cell.
• For $K > 0$, a level-$K$ carpet is a $3^K \times 3^K$ grid. When this grid is divided into nine $3^{K-1} \times 3^{K-1}$ blocks:
  • The central block consists entirely of white cells.
  • The other eight blocks are level-$(K-1)$ carpets.

You are given a non-negative integer $N$.
Print a level-$N$ carpet according to the specified format.

Constraints

• $0 \leq N \leq 6$
• $N$ is an integer.

Input

The input is given from Standard Input in the following format:

$N$

Output

Print $3^N$ lines.
The $i$-th line ($1 \leq i \leq 3^N$) should contain a string $S_i$ of length $3^N$ consisting of . and #.
The $j$-th character of $S_i$ ($1 \leq j \leq 3^N$) should be # if the cell at the $i$-th row from the top and $j$-th column from the left of a level-$N$ carpet is black, and . if it is white.

Sample Input 1

1

Sample Output 1

###
#.#
###

A level-$1$ carpet is a $3 \times 3$ grid as follows:

When output according to the specified format, it looks like the sample output.

Sample Input 2

2

Sample Output 2

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########

A level-$2$ carpet is a $9 \times 9$ grid.

问题描述

对于非负整数 $K$，我们定义一个级别为 $K$ 的地毯如下：

• 级别为 $0$ 的地毯是一个 $1 \times 1$ 的网格，包含一个黑色单元格。
• 对于 $K > 0$，级别为 $K$ 的地毯是一个 $3^K \times 3^K$ 的网格。当这个网格被分为九个 $3^{K-1} \times 3^{K-1}$ 的子块时：
  • 中间的子块完全由白色单元格组成。
  • 其他八个子块是级别为 $(K-1)$ 的地毯。

给你一个非负整数 $N$。
按照指定的格式打印一个级别为 $N$ 的地毯。

约束

• $0 \leq N \leq 6$
• $N$ 是一个整数。

输入

输入从标准输入以以下格式给出：

$N$

输出

打印 $3^N$ 行。
第 $i$ 行（$1 \leq i \leq 3^N$）应包含一个长度为 $3^N$ 的字符串 $S_i$，由 . 和 # 组成。
字符串 $S_i$ 的第 $j$ 个字符（$1 \leq j \leq 3^N$）应该是 #，如果一个级别为 $N$ 的地毯中，从上数第 $i$ 行，从左数第 $j$ 列的单元格是黑色的；否则是 .。

样例输入 1

1

样例输出 1

###
#.#
###

一个级别为 $1$ 的地毯是一个 $3 \times 3$ 的网格，如下所示：

按照指定的格式输出，看起来就像样例输出所示。

样例输入 2

2

样例输出 2

#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########

一个级别为 $2$ 的地毯是一个 $9 \times 9$ 的网格。