题目描述

哥萨克胡子得到了一个大小为 $n$ 乘 $m$ 的矩阵 $a$（即一个 $n$ 行 $m$ 列的矩阵）。该矩阵的元素仅为 $0$ 和 $1$。

有人向哥萨克介绍了矩阵中元素之间的曼哈顿距离。事实证明，如果一个元素位于第 $i$ 行第 $j$ 列，另一个元素位于第 $p$ 行第 $k$ 列，那么这两个元素之间的曼哈顿距离定义为 $\mid i - p \mid + \mid j - k \mid$（元素坐标差绝对值的和）。

之后，胡子明白了，矩阵中任何元素的 “美丽度” 是指该元素到最近一个值为 $1$ 的元素的距离。注意，任何 $1$ 的 “美丽度” 都为 $0$。此外，哥萨克还得知，在这样的矩阵中，至少存在一个 $1$。

你的任务很简单 —— 找出矩阵中最 “美丽” 的元素的 “美丽度”。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n,m \leq 20)$ —— 矩阵的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个数字 $a_{i,1}, a_{i,2},...,a_{i,m}$ $(0 \leq a_{i,j} \leq 1)$ —— 矩阵元素的值。

保证至少有一个 $1$。

输出格式

输出一个数字 —— 最大的 “美丽度”。

2 3
010
000

2

3 4
0101
0001
0000

3

提示

样例说明

对于第一个样例中的矩阵，将每个元素的 “美丽度” 写成矩阵形式：

:::align{center} 1 0 1

2 1 2 :::

如我们所见，有两个矩阵元素 —— （第二行，第一列）和（第二行，第三列）—— 拥有最大的 “美丽度”，为 $2$。

对于第二个样例，其 “美丽度” 矩阵为：

:::align{center} 1 0 1 0

2 1 1 0

3 2 2 1 :::

评分细则

在限制条件 $n = 1$ 下能正确运行的解决方案，将至少获得 $30$ 分。

在限制条件 $n = 2$ 下能正确运行的解决方案，将至少获得 $30$ 分。

翻译由 DeepSeek V3 完成