题目描述

给定一 $n \times m$ 的网格，其中每个格子均有颜色，可以为黑色或白色。

现可以进行若干次操作。一次操作中，你需选定上、下、左和右中的一个方向，然后，对于每个黑色的格子，若其指定方向上对应的位置不为网格的边界，则对应的那个格子变为黑色。

求：至少进行几次操作，才能使任意两个黑色格子八连通。八连通的定义可参考【提示/说明】部分。

输入格式

第一行两个整数 $n,m$（$1 \leq n,m \leq 10^3$），表示网格的大小。
接下来 $n$ 行，每行一个长为 $m$ 的 01 字符串，第 $i$ 个串的第 $j$ 位为 $1$ 则表示第 $i$ 行 $j$ 列的格子是黑色，否则是白色。

输出格式

一行一个整数，最少的操作次数。

5 4
1100
1000
0011
0000
0001

1

8 10
0000000011
0000000000
0000000000
0000000010
0000000000
0001010100
0000000000
0001000100

3

提示

【样例解释 #1】

对于第一组样例，一开始的网格如图（1）所示。

（1）

进行一次操作，选择下方向，网格会变为图（2）所示的样子（标红的是新变为黑色的格子），此时任意两个黑格都八连通。

（2）

【数据范围】

本题采用捆绑测试

• Subtask 1（$10$ 分）：保证 $n, m\leq 3$。
• Subtask 2（$10$ 分）：保证 $n, m \leq 80$。
• Subtask 3（$5$ 分）：保证黑色格子的数量不超过 $20$。
• Subtask 4（$5$ 分）：保证 $m = 1$。
• Subtask 5（$25$ 分）：保证 $n, m \leq 300$。
• Subtask 6（$45$ 分）：没有特殊限制。

对于 $100 \%$ 的数据，保证 $1 \leq n,m \leq 10^3$，至少有一个黑色格子。

八连通的定义

两个黑色格子八连通，当且仅当在它们之间有公共顶点或公共边，或存在一个黑色格子同时与它们八连通。

用比较通俗的话说，就是它们在只能向周围相邻的八个格子行走，且只能经过黑色格子的条件下相互可达。