测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A7350. 挖通湖泊(dig)

编程题 普及-
知识点

题目描述

X 国地理特征独特,用一个 $𝑛$ 行 $𝑚$ 列的二维网格表示。X国内有两个湖泊,其中一个湖泊在春夏水位暴涨,在秋冬水位下降;另外一个则是在秋冬水位暴涨,在春夏水位下降。一个湖泊由上下左右相邻的字符 '0' 网格组成。除了湖泊的网格外,都是地面网格,地面网格都是用字符 '1' 表示。

X 国为了保障国内的农耕活动,决定把两个湖泊挖通,以平衡水位。不过耕
地面积也很重要,X国希望能够保留尽可能多的地面网格数量。

于是这个重要的任务就落到了你身上,求在挖通两个湖泊后,X国能保留的
最大地面网格数。

输入格式

第一行 $2$ 个整数 $𝑛$、$𝑚$,表示网格的行数与列数。
接着 $𝑛$ 行,每行 $𝑚$ 个字符,其中字符 $0$ 表示湖泊网格、字符 $1$ 表示地面网格。

输出格式

输出仅 $1$ 个整数,表示挖通两个湖泊后,X国能保留的最大地面网格数。

输入输出样例

输入 #1
4 4
0111
1111
1111
1110
输出 #1
9
输入 #2
5 5 
00000 
01110 
01010 
01110 
00000 
输出 #2
7

说明/提示

### 样例解释
**样例一解释:**

二维网格情况如下图:

![](/uploads/acgo/image/045077e44e0bf04f_6c4f13281074.png)

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

![](/uploads/acgo/image/b840e478f1efde37_6d23805ca0eb.png)

剩下地面的网格数是 $9$ 格。

**样例二解释**

二维网格如下图。


![](/uploads/acgo/image/c46a2ee2507e36fd_503b6b93ea13.png)


只要挖掉湖2那个网格上、下、左、右相邻的其中任意一个网格就可以把
两个湖连通,此时地面网格数为 $7$。

### 数据范围

对于所有测试数据保证:$1≤𝑛,𝑚≤2000$。保证只有两个湖泊,保证两个湖
泊起始不连通。


| 测试点 | $n,m\leq$ |
|---|---|
| $1\sim2$ | $20$ |
| $3\sim4$ | $100$ |
| $5\sim6$ | $200$ |
| $7\sim8$ | $1000$ |
| $9\sim10$ | $2000$ |
上一题 去做题 下一题