Description

In a square grid consisting of digits $0$, there is a closed loop formed by digits $1$ of arbitrary shape. The task is to fill all spaces inside the closed loop with $2$. For example: for a $6 \times 6$ grid ($n = 6$), the grids before and after filling are as follows:

If starting from some $0$, moving only in the $4$ directions up, down, left, and right, and passing only through other $0$s, it is impossible to reach the boundary of the grid, then this $0$ is considered to be inside the closed loop. The closed loop is not necessarily ring-shaped; it can be any shape, but it is guaranteed that the $0$s inside the closed loop are connected (any two can reach each other).

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1

Input Format

For each test case, the first line contains an integer $n$ ($1 \le n \le 30$).

The next $n$ lines contain an $n \times n$ grid consisting of digits $0$ and $1$.

There is exactly one closed loop in the grid, and there is at least one $0$ inside the loop.

Output Format

Output the complete grid after filling the inside of the closed loop with the digit $2$.

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

Hint

For $100\%$ of the testdata, $1 \le n \le 30$.

Translated by ChatGPT 5