A116495.挖通湖泊(dig)
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
X 国地理特征独特,用一个 n 行 m 列的二维网格表示。X国内有两个湖泊,其中一个湖泊在春夏水位暴涨,在秋冬水位下降;另外一个则是在秋冬水位暴涨,在春夏水位下降。一个湖泊由上下左右相邻的字符 '0' 网格组成。除了湖泊的网格外,都是地面网格,地面网格都是用字符 '1' 表示。
X 国为了保障国内的农耕活动,决定把两个湖泊挖通,以平衡水位。不过耕
地面积也很重要,X国希望能够保留尽可能多的地面网格数量。
于是这个重要的任务就落到了你身上,求在挖通两个湖泊后,X国能保留的
最大地面网格数。
输入格式
第一行 2 个整数 n、m,表示网格的行数与列数。
接着 n 行,每行 m 个字符,其中字符 0 表示湖泊网格、字符 1 表示地面网格。
输出格式
输出仅 1 个整数,表示挖通两个湖泊后,X国能保留的最大地面网格数。
输入输出样例
输入#1
4 4 0111 1111 1111 1110
输出#1
9
输入#2
5 5 00000 01110 01010 01110 00000
输出#2
7
说明/提示
样例解释
样例一解释:
二维网格情况如下图:

挖通左上角的湖和右下角的湖至少需要 5 格,方案有很多,下面给出其中一
种:

剩下地面的网格数是 9 格。
样例二解释
二维网格如下图。

只要挖掉湖2那个网格上、下、左、右相邻的其中任意一个网格就可以把
两个湖连通,此时地面网格数为 7。
数据范围
对于所有测试数据保证:1≤n,m≤2000。保证只有两个湖泊,保证两个湖
泊起始不连通。
| 测试点 | n,m≤ |
|---|---|
| 1∼2 | 20 |
| 3∼4 | 100 |
| 5∼6 | 200 |
| 7∼8 | 1000 |
| 9∼10 | 2000 |