#396. 填涂颜色

    ID: 396 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>搜索深度优先搜索广度优先搜索洪水填充连通块CF

填涂颜色

题目描述

由数字 0 组成的方阵中,有若干任意形状的闭合圈,闭合圈由数字 1 构成。围圈时只考虑上、下、左、右四个方向相邻的格子。

现在需要将闭合圈内的所有 0 填涂为 2,而闭合圈外的 0 保持不变。所有原本为 1 的格子也保持不变。

给定一个 n×nn\times n 的方阵,请输出填涂后的结果。

例如下面的 6×66\times 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 1 1
1 1 1 1 1 0

填涂后:

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 1 1
1 1 1 1 1 0

输入格式

第一行包含一个整数 nn(1≤n≤301\le n\le30)。

接下来 nn 行,每行包含 nn 个整数,取值为 0 或 1,相邻整数之间用空格分隔。

输出格式

输出一个 n×nn\times n 的完整方阵:共 nn 行,每行 nn 个整数。被封闭的 0 变为 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 1 1
1 1 1 1 1 0

样例输出

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 1 1
1 1 1 1 1 0

提示

数据范围:1≤n≤301\le n\le30。

只有不能通过上下左右方向的 0 走到方阵边界的 0,才需要填成 2。仅在对角线上相接,不代表四方向连通。