UOJ Logo

NOI.AC

1S 512MB

#1297. 污染侵袭

Statistics

题目描述

在一个$n \times m$的格子矩阵上,每个格子上的数字是$0$或者$1$。 数字$1$表示格子已经被污染了,数字$0$表示格子是干净的。干净的格子可以通过上下左右四个方向和周围的干净格子连成一片干净的区域。如果这个干净的区域的周围完全被污染的格子包围,那么这片干净的区域中的所有的格子都会被污染。也就是这片区域所有格子上的数字都会变为$1$。

求最终这$n \times m$的格子矩阵的状态,每个格子是否被污染。

数据输入

第一行两个数字$n$和$m$。表示格子矩阵的大小。

接下来$n$行,每行$m$个用空格隔开的数字,每个数字非0即1.表示是否被污染。

数据输出

输出$n$行,每行$m$个用空格隔开的数字,行末无空格。每个数字非$0$即$1$,表示格子相应格子是否被污染。

样例输入1

4 4
0 1 1 1
0 1 0 1
1 0 0 1
1 1 1 0

样例输出1

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

样例输入2

2 2
0 1
1 0

样例输出2

0 1
1 0

范围说明

对于$30\%$的数据有:$1 \leq n, m \leq 20$。

对于$100\%$的数据有:$1 \leq n, m \leq 1000$。