Programming Problem #28
"Wetlands"

Real estate developers who intend to develop in the wetlands of Florida buy large rectangular tracts of land and then divide them into square lots so that each lot is entirely land or entirely water. Adjacent water lots will be combined into one large lake. Given the location of a water lot within a tract, a developer wants to know the area of the largest possible lake containing that lot. Lots are considered to be adjacent if they share a common side or corner.

The input will contain the dimensions of the tract of land, a map of the land, and the location of one or more water lots. The first line will contain R and C, the number of rows and columns in the map, separated by a space. The minimum map size is 1x1, and the maximum map size is 100x100. The next R lines will each contain a string of C characters beginning in column 1. Each character will be either `*', indicating dry land, or 'W', indicating water. The remaining lines will each contain the row and column of a water lot; for each of these lines, output the area of the largest possible lake containing that lot as shown in the example.

Input must be read from the file "prob28.in", and output must be written to the file "prob28.out". All output to the screen will be ignored.

Example Input

<BOF>
10 12
****W***W***
**W*WW****W*
**WWW***WW**
***W**W***W*
***WW*W***W*
****W*****W*
***WWW**W***
*****W*****W
*WW**W****W*
*WW***WWWW**
3 4
7 9
10 2
<EOF>

Example Output

22
1
4
A version of this problem originally appeared in the 1991 Florida International University/University of Central Florida programming contest.

Dr. Eric Shade