#10721. 矩阵距离

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

给定一个 n×m 01 矩阵:

a_{11} a_{12} ... a_{1m} ... a_{n1} a_{n2} ... a_{nm} 定义 a_{ij} a_{kl} 之间的距离为 D(a_{ij},a_{kl})=|i−k|+|j−l|

对于每个元素 a_{ij} ,请求出与它距离最近且值为 1 的元素 a_{kl} 和它的距离是多少。

另外注意,当元素 a_{ij} 本身就为 1 时,与它距离最近且值为 1 的元素就是它自己,距离为 0

输入格式

第一行为两个整数,分别代表 n m

接下来的 n 行,第 i 行的第 j 个字符代表 a_{ij}

输出格式

n 行,第 i 行的第 j 个数字表示 a_{ij} 与其距离最近且值为 1 的元素的距离。

样例

输入样例:

3 4
0001
0011
0110

输出样例:

3 2 1 0
2 1 0 0
1 0 0 1

数据范围与提示

1≤n,m≤1000