时间限制: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 个整数,表示校园的初始布局,0 表示建筑单元,1 表示水域单元。
输出描述:
输出一个整数,表示至少需要的天数。
示例1
输入
复制
3 5
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0