A116495.挖通湖泊(dig)

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例

  • 输入#1

    4 4
    0111
    1111
    1111
    1110

    输出#1

    9
  • 输入#2

    5 5 
    00000 
    01110 
    01010 
    01110 
    00000 

    输出#2

    7

说明/提示

样例解释

样例一解释:

二维网格情况如下图:

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

剩下地面的网格数是 99 格。

样例二解释

二维网格如下图。

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

数据范围

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

测试点 n,mn,m\leq
121\sim2 2020
343\sim4 100100
565\sim6 200200
787\sim8 10001000
9109\sim10 20002000
首页