Black Marbles

0

0 votes
Problem

There is a grid of size M X N. Each point of the grid could be free, occupied by a black marble or by a white marble. If a black marble is placed at point (x,y) then no other black marble could be placed at points (x-2, y-2), (x-2, y+2), (x+2, y-2) and (x+2, y+2) unless there is a white marble exactly in the middle.

Ex: We could place two black marbles at point (x,y) and (x+2,y+2) if and only if there is a white marble at point (x+1,y+1).

Given a grid with some points which has been occupied by black marbles or white marbles your task is to find out the greatest number of black marbles to add to this grid satisfying rules above. Note that we can put a black marble at a free point, but we cannot remove any black marble and white marble, and we cannot add white marble.

Input

There are several test cases, each formed as follows:

i) The first line contains two positive integer M, N.

ii) Next M lines, each contains N characters (no spaces) of {'F', 'G', 'P'} (ASCII: #70, #71, #80), the j-th character of the i-th line represents the point (i-1, j-1) on the grid: 'F' is a free point, 'G' is occupied by a black marble and 'P' is occupied by a white marble.

The input is ended with M = N = 0.

Output

For each test case, output on a line the greatest number of black marbles which can be added to the given grid.

Constraints

M>0, N<701

The sum of MxN does not exceed 490000 in one judge file.

Time Limit: 10
Memory Limit: 100
Source Limit:
Editor Image

?