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

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

剩下地面的网格数是9格。
二维网格如下图。

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