A7350. 挖通湖泊(dig)
编程题
普及-
知识点
题目描述
X 国地理特征独特,用一个 $𝑛$ 行 $𝑚$ 列的二维网格表示。X国内有两个湖泊,其中一个湖泊在春夏水位暴涨,在秋冬水位下降;另外一个则是在秋冬水位暴涨,在春夏水位下降。一个湖泊由上下左右相邻的字符 '0' 网格组成。除了湖泊的网格外,都是地面网格,地面网格都是用字符 '1' 表示。
X 国为了保障国内的农耕活动,决定把两个湖泊挖通,以平衡水位。不过耕
地面积也很重要,X国希望能够保留尽可能多的地面网格数量。
于是这个重要的任务就落到了你身上,求在挖通两个湖泊后,X国能保留的
最大地面网格数。
X 国为了保障国内的农耕活动,决定把两个湖泊挖通,以平衡水位。不过耕
地面积也很重要,X国希望能够保留尽可能多的地面网格数量。
于是这个重要的任务就落到了你身上,求在挖通两个湖泊后,X国能保留的
最大地面网格数。
输入格式
第一行 $2$ 个整数 $𝑛$、$𝑚$,表示网格的行数与列数。
接着 $𝑛$ 行,每行 $𝑚$ 个字符,其中字符 $0$ 表示湖泊网格、字符 $1$ 表示地面网格。
接着 $𝑛$ 行,每行 $𝑚$ 个字符,其中字符 $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≤𝑛,𝑚≤2000$。保证只有两个湖泊,保证两个湖
泊起始不连通。
| 测试点 | $n,m\leq$ |
|---|---|
| $1\sim2$ | $20$ |
| $3\sim4$ | $100$ |
| $5\sim6$ | $200$ |
| $7\sim8$ | $1000$ |
| $9\sim10$ | $2000$ |
**样例一解释:**
二维网格情况如下图:

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

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

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