校园改造计划
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

🍃同学突发奇想:如果把学校抽象成一个 n × m 的二维网格,用 0 表示建筑单元,用 1 表示水域单元,那么校园的布局会是怎样的呢?

在调研了一番后,他发现学校的水域面积太大了,准备对水域单元进行改造,用来建设新的建筑。但是他能力有限,一天内对于同一个连通块内的水域单元只能把 1 个水域单元改为 1 个为建筑单元。

🍃同学定义:任意两块单元之间可以通过上下左右四方向到达,则认为是连通的,否则认为是分离的。

他希望改造后,校园里会出现多个水域单元分离(即水域被分成至少两个互不连通的区域),他想知道至少需要多少天,才会出现多块个水域单元分离?

注:如果网格中全是建筑(没有水域),也认为已经出现了多个水域单元分离。

(¥还是太多了)

输入描述:

第一行两个正整数n,m(1 \leq n, m \leq 200),表示网格大小
接下来 n 行,每行 m 个整数,表示校园的初始布局,0 表示建筑单元,1 表示水域单元。

输出描述:

输出一个整数,表示至少需要的天数。
示例1

输入

复制
3 5
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

输出

复制
2
示例2

输入

复制
1 2
1 1

输出

复制
2