Mirko has been learning to drive, but he still cannot make a U-turn in a narrow street. That's why he has decided to go practice in a town where U-turns are forbidden everywhere. This prohibition can be marked by the following sign:
Mirko has soon figured out that his ideal town must not contain dead-end streets, since it is impossible to exit such a street without a U-turn (let us assume that Mirko cannot drive in reverse either). Write a program to analyse a town map and determine whether the town is suitable for Mirko (i.e. whether the town has any dead-end streets).
The town map is a table with cells, where each cell is a building segment (denoted by X
) or a
road surface (denoted by a dot). From a road surface cell, Mirko can move to any of the surrounding
four cells (up, down, left, or right), provided that it is also a road surface (i.e. not a building).
Formally, we will determine that a town is free of dead-end streets if, starting from any road surface cell and going in any of the possible directions, we can return to the starting cell without making a degrees turn (changing our direction to the opposite one).
Input Specification
The first line of input contains the positive integers and , the dimensions of the town.
Each of the next lines contains characters, with each character either X
or .
. These
characters represent the town map as described in the text above. At least two cells will be road
surfaces, and all road surfaces will be connected (i.e. mutually reachable).
Output Specification
The first and only line of output must contain if the town is free of dead-end streets, otherwise it must contain .
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
Comments