题目描述

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

• Initially each cell of the grid is either empty or occupied.
• Players take turns placing a stone on an empty cell, occupying the cell. Each new stone must be adjacent to the last placed stone, with the exception of the starting stone that can be placed on any empty cell. A stone is adjacent to another stone if they are located in two cells that share a side.
• The game ends whenever a player cannot place a stone according to the above rules. In that case, the player who cannot place a stone loses the game, and the other player wins.

A winning starting cell is a cell such that the first player wins the game if they place their starting stone there, assuming both players play optimally. Given a description of the initial grid, you must tell how many winning starting cells it has.

输入格式

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 50$) indicating the dimensions of the grid.

Each of the next $N$ lines contains a string of length $M$. In the $i$-th string, the $j$-th character describes the initial state of cell $(i, j)$. The character is either "." (dot) denoting an empty cell, or "#" (hash) representing an occupied cell.

输出格式

Output a single line with an integer indicating the number of winning starting cells.

3 3
#.#
...
#.#

4

3 3
..#
...
...

0

1 4
...#

2