Andy is very bad at chess, and his friend bullies him by making him play Chinese chess. Andy has never played Chinese chess before and is very confused about how the Cannon Pieces work. The Cannon Piece can take a piece only if there is exactly one other piece between the Cannon Piece and that piece on the same row or column. For example, let c
denote the Cannon Piece, .
denote blank space, and *
represent any other pieces:
c....*...*
The Cannon Piece can take the piece at the end of the row. (It's worth noting that it also works for columns.)
The Chess board is an grid. Can you help Andy determine the total number of positions he can place the Cannon Piece such that the Cannon Piece can take a piece on the next turn? It is important to note that a valid position cannot already have a piece on it.
Constraints
For all subtasks:
Every character in the grid is either .
or *
.
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line contains two integers and
, the number of rows and columns.
The following lines describe the grid, with
characters in each line.
Output Specification
Output the number of positions such that if the Cannon Piece is placed there, it can take a piece on the next move.
Sample Input
5 5
..*..
.....
.*.**
*..*.
.*.*.
Sample Output
9
Sample Explanation
Valid points are denoted with the symbol c
:
.c*c.
.c.c.
c*c**
*..*c
c*.*c
Comments