#T. 矩阵距离

Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 $N$ 行 $M$ 列的 $0-1$ 矩阵 $A$ ， $A[i][j]$ 与 $A[k][l]$ 之间的曼哈顿距离定义为：

dist(A[i][j],A[k][l])=|i-k|+|j-l|

求一个与矩阵 $A$ 大小相同的矩阵 $B$ ，其中：

$$B[i][j]=\min_{1 \le x \le N,1 \le y \le M,A[x][y]=1} dist(A[i][j],A[x][y]) $$

第一行，两个整数 $N,M$ ，中间用一个空格隔开。随后有 $N$ 行，每行 $M$ 个数，表示矩阵 $A$ 。

$N$ 行，每行 $M$ 个数，表示矩阵 $B$ 。

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

$1 \le N,M \le 1000$ 。