P7274 草地

给定一 $n \times m$ 的网格，其中每个格子均有颜色，可以为黑色或白色。 现可以进行若干次操作。一次操作中，你需选定上、下、左和右中的一个方向，然后，对于每个黑色的格子，若其指定方向上对应的位置不为网格的边界，则对应的那个格子变为黑色。 求：至少进行几次操作，才能使任意两个黑色格子八连通。八连通的定义可参考【提示/说明】部分。

无

无

---- **【样例解释 #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$，至少有一个黑色格子。 **八连通的定义** 两个黑色格子八连通，当且仅当在它们之间有公共顶点或公共边，或存在一个黑色格子同时与它们八连通。 用比较通俗的话说，就是它们在只能向周围相邻的八个格子行走，且只能经过黑色格子的条件下相互可达。