No U-Turns

Time limit1sMemory limit128 MB

Summary

Given a grid with roads and buildings, decide if every road cell is free of dead ends by checking whether from each road cell you can return without an immediate U-turn.

Level: Medium6 of 10
Topics: Graph, DFS, Implementation
Solved: No attempts yet

Problem

Sanggeun learned to drive so he could go on drives with his girlfriend. He has become comfortable behind the wheel, but he still cannot make U-turns. Instead of spending more time practicing them, he wants to move to a town where U-turns are unnecessary and prohibited.

The town must not contain any dead ends. If he enters a dead end, he cannot get out without making a U-turn. Given a map of the town, determine whether every road area can be traveled without making a U-turn; equivalently, determine whether the town contains a dead end.

The town map is an R × C grid. Each cell is marked X if it is a building and . if it is a road. From a road cell, he may move to an adjacent road cell in one of the four directions: up, down, left, or right. He cannot move into a building.

If the town has no dead ends, then from any road cell, after moving to any adjacent road cell, he must be able to return to that position without making a U-turn.

A U-turn means immediately moving in the exact opposite direction from the previous move.

Input

The first line contains the town size R and C. (3 ≤ R, C ≤ 10)

The next R lines contain the town map. All road cells are connected to one another, and the town contains at least two road cells.

Output

Print 0 if the town has no dead ends. Otherwise, print 1.

Examples3

Example 1
Input
```
4 3
XXX
X.X
X.X
XXX
```
Expected output
```
1
```
Example 2
Input
```
5 5
XX.XX
X...X
.....
X...X
XX.XX
```
Expected output
```
1
```
Example 3
Input
```
3 9
...XXX...
.X.....X.
...XXX...
```
Expected output
```
0
```