Maze Escape

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.

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.

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