103752: [Atcoder]ABC375 C - Spiral Rotation

Problem Statement

You are given a grid with $N$ rows and $N$ columns, where $N$ is an even number. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.

Each cell is painted black or white. If $A_{i, j} =$ #, cell $(i, j)$ is black; if $A_{i, j} =$ ., it is white.

Find the color of each cell after performing the following operation for $i = 1, 2, \ldots, \frac{N}{2}$ in this order.

• For all pairs of integers $x, y$ between $i$ and $N + 1 - i$, inclusive, replace the color of cell $(y, N + 1 - x)$ with the color of cell $(x, y)$. Perform these replacements simultaneously for all such pairs $x, y$.

Constraints

• $N$ is an even number between $2$ and $3000$, inclusive.
• Each $A_{i, j}$ is # or ..

Input

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

$N$
$A_{1,1}A_{1,2}\ldots A_{1,N}$
$A_{2,1}A_{2,2}\ldots A_{2,N}$
$\vdots$
$A_{N,1}A_{N,2}\ldots A_{N,N}$

Output

After all operations, let $B_{i, j} =$ # if cell $(i, j)$ is black, and $B_{i, j} =$ . if it is white. Print the grid in the following format:

$B_{1,1}B_{1,2}\ldots B_{1,N}$
$B_{2,1}B_{2,2}\ldots B_{2,N}$
$\vdots$
$B_{N,1}B_{N,2}\ldots B_{N,N}$

Sample Input 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

Sample Output 1

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

The operations change the colors of the grid cells as follows:

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

Sample Input 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

Sample Output 2

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

Sample Input 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

Sample Output 3

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

问题陈述

给定一个有N行和N列的网格，其中N是一个偶数。令$(i, j)$表示从顶部第i行和从左边第j列的单元格。

每个单元格被涂成黑色或白色。如果$A_{i, j} =$ #，单元格$(i, j)$是黑色的；如果$A_{i, j} =$ .，它是白色的。

在按顺序对$i = 1, 2, \ldots, \frac{N}{2}$执行以下操作后，找出每个单元格的颜色。

• 对于所有整数对$x, y$在$i$和$N + 1 - i$之间（包括），将单元格$(y, N + 1 - x)$的颜色更改为单元格$(x, y)$的颜色。对所有这样的对$x, y$同时执行这些替换。

约束条件

• $N$是一个在2到3000之间（包括）的偶数。
• 每个$A_{i, j}$是#或.。

输入

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

$N$
$A_{1,1}A_{1,2}\ldots A_{1,N}$
$A_{2,1}A_{2,2}\ldots A_{2,N}$
$\vdots$
$A_{N,1}A_{N,2}\ldots A_{N,N}$

输出

在所有操作之后，令$B_{i, j} =$ #如果单元格$(i, j)$是黑色的，且$B_{i, j} =$ .如果它是白色的。按以下格式打印网格：

$B_{1,1}B_{1,2}\ldots B_{1,N}$
$B_{2,1}B_{2,2}\ldots B_{2,N}$
$\vdots$
$B_{N,1}B_{N,2}\ldots B_{N,N}$

示例输入1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

示例输出1

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

操作改变了网格单元格的颜色如下：

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

示例输入2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

示例输出2

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

示例输入3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#