2159: 猫鼠大战

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：1 Solved：1

Description

猫鼠大战进入最后收官阶段。在由 1与 0组成的 n*n 的方阵中，1表示猫，0表示鼠，最终猫围成了一个大包围圈，是下列方阵中 1组成的任意形状的闭合圈，围圈时只走上下左右4个方向。现要求把闭合圈内的所有0都改写成2。闭合圈中 0都是相邻的，也是指上下左右4个方向。

请你用BFS算法编写程序完成。

Input

第一行包含 1 个整数 n，之后 n 行，由  和  组成的  的方阵。

方阵内只有一个闭合圈，圈内至少有一个 0 。

Output

改写好数字  的 n*n 的完整方阵。

Sample Input Copy 

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

Sample Output Copy 

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

HINT

1<n<=30