A7350 | 挖通湖泊(dig)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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$ |
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?