Summer Institute '17 Contest 1 P9 - Safe Square

View as PDF

Submit solution

Points: 7
Time limit: 1.4s
Memory limit: 256M

Problem type

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, r (1 \le r \le 100) and c (1 \le c \le 100, rc > 1), the number of rows and columns, respectively, on the grid in which Simon lives. The following r lines contain c characters each, either . or S. A dot (.) indicates a square without a snake and S indicates a square with a snake. The j^\text{th} character on the i^\text{th} of these lines represents the contents of the square on row i, column j 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

There are no comments at the moment.