Simon lives in a rectangular grid. At any given time, he occupies a single square on the grid. Some of the squares on the grid he lives in have snakes and he can not occupy those squares. In fact, he dislikes snakes so much, that he prefers not to occupy any square where half or more of the adjacent squares contain snakes. Two squares are adjacent if they share a corner, so the maximum number of squares adjacent to any square is 8. Simon considers these squares to be dangerous squares, as well as squares with snakes. He considers all other squares to be safe squares. Help Simon figure out how many squares on the grid in which he lives are safe squares.
Input Specification
The first line of input contains two space separated integers, and ,
the number of rows and columns, respectively, on the grid in which Simon lives. The
following lines contain characters each, either .
or S
. A dot (.
) indicates a square without a
snake and S
indicates a square with a snake. The character on the of these lines
represents the contents of the square on row , column of the grid in which Simon lives.
Output Specification
Output a single integer representing the number of safe squares on the input grid in which Simon could live.
Sample Input 1
3 5
.....
S.S.S
SS.S.
Sample Output 1
6
Sample Input 2
5 6
S.S.S.
.S.S.S
S.S.S.
.S.S.S
S.S...
Sample Output 2
4
Comments