C - Sierpinski carpet Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250 点

問題文

非負整数 K に対して、以下のようにレベル K のカーペットを定義します。

  • レベル 0 のカーペットは黒いマス 1 個のみからなる 1\times 1 のグリッドである。
  • K>0 のとき、レベル K のカーペットは 3^K\times 3^K のグリッドである。 このグリッドを 3^{K-1}\times 3^{K-1} のブロック 9 個に分割したとき、
    • 中央のブロックはすべて白いマスからなる。
    • 他の 8 個のブロックは、レベル (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 のグリッドとなります。

Score : 250 points

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.