Feeding Time

Interview

Time limit1sMemory limit128 MB

Summary

Given a W by H grid of grass and rock, find the size of the largest connected grass region using 8-directional adjacency.

Level: Easy3 of 10
Topics: DFS, BFS, Graph, Matrix
Solved: No attempts yet

Problem

It is Bessie the cow's feeding time, and the farmer is trying to decide which pasture to put her in. The farm is a grid of $W \times H$ squares ( $1 \le W \le 750$ , $1 \le H \le 750$ ) and is partitioned into one or more separate pastures by rocks both large and small. Every square is either grass or rock.

Bessie is a hungry little cow and just loves to eat, eat, eat her grass. She can move from any square to any other square that is horizontally, vertically, or diagonally adjacent (that is, in any of the eight directions). Bessie cannot cross rock squares because they hurt her feet, and she cannot leave the farm. Bessie wants to know the maximum number of grass squares she can eat in a single feeding.

On the map, . represents a grass square and * represents a rock. Below is an example $10 \times 8$ map together with a detailed breakdown of its three pastures (each pasture labeled with a digit 1, 2, or 3).

      ...*....**  |  111*....**   ...*2222**    ...*....**
      ..**....**  |  11**....**   ..**2222**    ..**....**
      ...*....**  |  111*....**   ...*2222**    ...*....**
      ...**.*.**  |  111**.*.**   ...**2*2**    ...**.*.**
      ***.**.***  |  ***1**.***   ***.**2***    ***.**.***
      ...**.*.**  |  111**.*.**   ...**2*2**    ...**.*.**
      ...*.*****  |  111*.*****   ...*2*****    ...*.*****
      ...***..**  |  111***..**   ...***..**    ...***33**

Pasture 1 has 21 squares, pasture 2 has 18 squares, and pasture 3 has 2 squares. Thus Bessie should choose pasture 1 with 21 squares to maximize the grass she can eat.

A pasture is a maximal set of grass squares connected to one another in the eight directions. Print the number of grass squares in the largest pasture.

Input

Line 1: Two space-separated integers $W$ and $H$ .
Lines 2.. $H+1$ : Line $i+1$ describes row $i$ with $W$ characters and no spaces, each either . (grass) or * (rock).

Output

Line 1: A single integer, the maximum number of grass squares Bessie can eat within one pasture.

Examples6

Example 1

Input

10 8
...*....**
..**....**
...*....**
...**.*.**
***.**.***
...**.*.**
...*.*****
...***..**

Expected output

Example 2
Input
```
1 1
.
```
Expected output
```
1
```
Example 3
Input
```
1 1
*
```
Expected output
```
0
```
Example 4
Input
```
3 3
...
...
...
```
Expected output
```
9
```
Example 5
Input
```
2 2
.*
*.
```
Expected output
```
2
```
Example 6
Input
```
5 1
.*.*.
```
Expected output
```
1
```