Clever Cell Choices

Time limit6sMemory limit1024 MB

Summary

Count the empty cells where the first player, placing the opening stone there, wins the game of alternately placing stones on side-adjacent empty cells.

Level: Medium7 of 10
Topics: Graph, BFS
Solved: No attempts yet

Problem

Two players play the following game on an $N \times M$ grid:

Initially each cell is either empty or occupied.
Players take turns placing a stone on an empty cell, occupying it. Each new stone must be placed on a cell that shares a side with the last placed stone. The starting stone may be placed on any empty cell.
A player who cannot place a stone by these rules loses, and the other player wins.

A winning starting cell is a cell where the first player places the starting stone and wins when both players play optimally. Given the initial grid, count the winning starting cells.

Input

The first line contains two integers $N$ and $M$ ( $1 \le N, M \le 50$ ), the dimensions of the grid. Each of the next $N$ lines contains a string of length $M$ . The $j$ -th character of the $i$ -th string describes cell $(i, j)$ : . is an empty cell and # is a cell with a stone.

Output

Output a single integer, the number of winning starting cells.

Examples3

Example 1
Input
```
3 3
#.#
...
#.#
```
Expected output
```
4
```
Example 2
Input
```
3 3
..#
...
...
```
Expected output
```
0
```
Example 3
Input
```
1 4
...#
```
Expected output
```
2
```