题目描述

给定一个 $n×m$ 的二元矩阵，其中 1 代表黑色单元格，0 代表白色单元格。每一秒，每个黑色单元格会将其上、下、左、右四个相邻的白色单元格变为黑色。

你可以将最多一个白色单元格变为黑色（将 0 变为 1），以最小化整个矩阵完全变黑所需的时间。求 出这个最短时间。

输入格式

第一行包含两个整数 $n$ 和 $m(1⩽n×m⩽2×10^5)$，表示矩阵的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个数字（0 或 1），表示矩阵的初始状态。

输出格式

输出一个整数，表示在增加一个黑色单元格后，使整个矩阵变黑所需的最短时间。

3 3
0 0 0
0 0 0
0 0 1

2

解释 #1

对于样例 1,您可以选择位置 $(1,1)$。

第 $0$ 秒时的矩阵：

1 0 0
0 0 0
0 0 1

第 $1$ 秒时的矩阵：

1 1 0
1 0 1
0 1 1

第 $2$ 秒时的矩阵：

1 1 1
1 1 1
1 1 1