Skip to content

UKSPC Practice Problems » Wetlands of Florida

A construction company owns a large piece of real estate within Florida. Recently, the company decided to develop this property. Upon inspection of the property, however, it was revealed that the land, at various locations, contained bodies of water. This came as a shock to the owners of the company, because they were from out of state and not familiar with Florida's wetlands. The situation was very grave and the owners, not knowing that such bodies of water can be converted to beautiful lakes that will increase the value of the land around them, were about to abandon the construction project. Fortunately, this fact was brought to the owners' attention by a smart FIU graduate who worked for the company; consequently, the construction project started.

The engineers divided the construction site into uniform square cells such that each square cell entirely contained either water or land. (How they did it, of course, is anybody's guess.) Now, the question that the engineers are to answer is the following: given the row and column number of a grid cell that contains water, what is the area of the lake containing that cell? An area is measured by number of grid cells it contains.

You are to write a program to answer this question.

Input Specification

The input consists of 0 < n ≤ 99 lines each containing a 0 < m ≤ 99-character long sequence of 'L's and 'W's followed by k > 0 lines each containing a pair of integers i and j. The first n lines will represent the n by m grid covering the land where a 'W'/'L' at the c. character of the r. line indicates water/land within the cell at row r and column c of the grid. The pairs of integers on the last k lines each represent the row and column numbers of some grid cell that contains water.

Output Specification

The output for each pair of integers, i and j, on the last k lines of input consists of an integer on a separate line, indicating the area of the lake containing the grid cell at row i and column j of the grid.

Sample Input

LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLLLWLLLL
LLLLLLLLL
3 2
7 5
0 0

Sample Output

12
3