#P2048. 卫星照片 USACO 2005 NOV

卫星照片 USACO 2005 NOV

题目描述

农场主约翰给他的农场买了 W×HW \times H 像素的卫星照片(1W801 \leq W \leq 801H10001 \leq H \leq 1000),希望找出最大的“连续的”(互相连接的)牧场。对于一个牧场的任何一对像素,其中一个像素如果能横向的或纵向的与属于这个牧场的另一个像素相连,这样的牧场称作是连续的。(很容易创建形状稀奇古怪的牧场,甚至是围着其它圆圈的圆圈。)

每一张照片都数字化的抽象了,牧场区显示为*,非牧场区显示为.。下面是一个 10×510 \times 5 的卫星照片样例:

..*.....**
.**..*****
.*...*....
..****.***
..****.***

这张照片显示了大小分别为4、16、6个像素的连续牧场区。帮助农场主约翰在他的每张卫星照片中找到最大的连续牧场。

输入格式

第 1 行:两个由空格分开的整数,WWHH。 第 2 到 H+1H+1 行:每一行包含 WW*或者.,代表卫星照片的横向行。

输出格式

输出一个整数,表示最大连续牧场的大小。

样例

样例输入 1

10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***

样例输出 1

16

数据范围

对于 100%100\% 的数据,1W801 \leq W \leq 801H10001 \leq H \leq 1000