Maze Escape

Time limit2sMemory limit128 MB

Summary

Find the minimum time to escape a maze where the player can press a button to rotate an entire row and column of rooms by 90 degrees, changing their door layout.

Level: Medium6 of 10
Topics: BFS, Bit manipulation, Simulation, Math
Solved: No attempts yet

Problem

Sejun is trapped in a rectangular maze and wants to move from the upper-left room to the lower-right room. The maze consists of 1 x 1 rooms. Each side of a room may or may not have a door.

Each room is one of four types:

A: doors on all four sides
B: no doors
C: doors only on the top and bottom sides
D: doors only on the left and right sides

To move between two adjacent rooms, both doors must exist: the current room must have a door in the direction of movement, and the destination room must have a door on the opposite side. For example, moving upward is possible only when the current room has a top door and the room above it has a bottom door.

The maze is surrounded by solid walls, so it is impossible to leave the maze even if an outer side has a door. Moving from one room to an adjacent room takes 1 second.

The maze may not initially have enough doors for Sejun to reach the destination. Sejun has a button that can adjust the maze. When he presses it, every room in his current row rotates by 90 degrees, and every room in his current column also rotates by 90 degrees. The room where Sejun is standing is in both the row and the column, so it rotates twice and its shape remains unchanged. A 90 degree rotation changes a top door into a right door.

Pressing the button also takes 1 second.

Find the minimum time needed to reach the lower-right room from the upper-left room.

Input

The first line contains the maze height N and width M. Both N and M are integers between 2 and 7, inclusive.

The next N lines each contain a string of length M describing one row of the maze. Each character is one of A, B, C, and D.

Output

Print the minimum time required for Sejun to reach the destination. If it is impossible, print -1.

Examples6

Example 1
Input
```
2 7
ACDCDCA
BBBBBBA
```
Expected output
```
12
```
Example 2
Input
```
2 2
AA
AA
```
Expected output
```
2
```
Example 3
Input
```
5 3
AAA
BBA
AAA
ABB
AAA
```
Expected output
```
10
```
Example 4
Input
```
2 7
AAACAAA
BBBBBBA
```
Expected output
```
8
```
Example 5
Input
```
2 2
CA
BA
```
Expected output
```
-1
```
Example 6
Input
```
3 3
CAA
DAA
ACA
```
Expected output
```
6
```