| Segmenting binary images |
A basic problem in the processing of binary images is segmentation. This involves finding connected components of black pixels. Since a binary image is a 2-d array of B's and W's, we need to define the neighborhood of a pixel first. In this problem, we assume that a pixel may have up to 8 neighbors (left, right, top, bottom and the 4 diagonals). The question that your program needs to answer is ``Given the row and column number of a pixel that is black, what is the area of the segment containing that pixel?'' (area is measured as the number of pixels it contains). To make the problem easier, you may assume that the segments are convex (this means that if two pixels are black, any pixel on the line joining them must be black). Note that this implies that you cannot have a black segment enclosing a region of white pixels.
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
Each input set starts with a line containing 2 numbers -- number of rows r and columns c in the image. You may assume that r,c are positive and no more than 100. The next r lines contains c characters each, the characters being B or W. The next line contains n, the number of queries about the image. The next n lines contain one pair of integers each, representing the row and column numbers of some pixel that is black. Note that rows and columns are numbered from 0, the top row is numbered 0 and the leftmost column is numbered 0.
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output for each pair of integers, i and j, on the last n lines of input, consists of an integer, on a separate line, indicating the area of the segment containing the pixel at row i and column j of the image.
1 5 5 BBBBB WWWWW BBBWW BBWWW BWWWW 2 0 1 3 0
5 6