Problem Description

Given a map of size $R \times C$, where . denotes a walkable cell and X denotes a non-walkable cell. Determine if the map contains any dead ends.

A cell is considered a dead end if it has exactly one adjacent cell (up, down, left, or right) that is walkable. Note that walking outside the map is not allowed.

Input Format

The first line of input contains two positive integers, $R$ and $C$.

The following $R$ lines each contain $C$ characters, describing the map.

Output Format

Output 1 if the map contains a dead end, otherwise output 0.

Sample Input and Output

Sample Input #1

4 3
XXX
X.X
X.X
XXX

Sample Output #1

1

Sample Input #2

5 5
XX.XX
X...X
.....
X...X
XX.XX

Sample Output #2

1

Sample Input #3

3 9
...XXX...
.X.....X.
...XXX...

Sample Output #3

0

Notes

Data Range

For $100\%$ of the data, $3 \le R,C \le 10$.

Notes

This problem is scored according to the original COCI settings, with a maximum score of $80$.

The problem is translated from COCI2011-2012 CONTEST #2 T2 OKRET.

见题面 Input 部分

见题面 Output 部分