bzoj#P2252. [2010Beijing wc]矩阵距离

[2010Beijing wc]矩阵距离

题目描述

假设我们有矩阵,其元素值非 0011

a1,1a1,ma_{1,1} \dots\dots a_{1,m}

\dots\dots\dots\dots\dots

an,1an,ma_{n,1} \dots\dots a_{n,m}

定义 ai,ja_{i,j}ak,la_{k,l} 之间的距离为 D(ai,j,ak,l)=abs(ik)+abs(jl)D(a_{i,j},a_{k,l})=abs(i-k)+abs(j-l)

输入格式

输入文件的第一行为两个整数,分别代表 nnmm

接下来的 nn 行,第 ii 行的第 jj 个字符代表 ai,ja_{i,j}

输出格式

输出包含 nn 行,每行 mm 个用空格分开的数字,其中第 ii 行第 jj 个数字代表:

Min(D(ai,j,ax,y))Min(D(a_{i,j},a_{x,y}))1xn1 \le x \le n1ym1 \le y < m,且 ax,y=1a_{x,y}=1

3 4
0001
0011
0110
3 2 1 0
2 1 0 0
1 0 0 1

数据规模与约定

100%100\% 的数据满足:0m,n1×1030 \le m,n \le 1 \times 10^3