PEG Test – Oct 3rd, 2014

It's been over 70 years since the events of Sozin's comet. Republic city is thriving from the legacy of Avatar Aang. The young and restless Korra must start anew in her service to the world as the next avatar. At only seventeen years old, Korra has effectively mastered all the elements except for airbending. Starting her airbending training with Aang's son, Tenzin, Korra is hoping to finally overcome her lifelong struggle.

Being an airbender is all about building up the instinct to avoid and evade conflicts, following the path of least resistance. Airbenders train to be highly defensive, moving about their environment and opponents like the wind. To practice being evasive, ancient training devices called airbending gates are used. Each gate is simply a tall board that stands upright with respect to the ground. The gates rotate according to the wind, and it is Korra's job to navigate the course of gates without being beaten up by a bunch of boards. The key is to be as gentle and adaptive as a leaf through the wind.

The entire obstacle course can be seen as a grid with ~N~ rows and ~M~ columns ~(1 \le N, M \le 100)~. Row ~1~ is the northmost row, row ~N~ is the southmost row, column ~1~ is the westmost column, and column ~M~ is the eastmost column. Gates are positioned at certain places on this grid. For the sake of simplicity, we can assume that gates are always facing ~45^\circ~ with respect to the borders of the grid. That is, initially, a gate can either be oriented like /, or \. To make it even harder for Korra, the wind will simultaneously flip the orientation of every gate during every second.

Korra starts the course on the north-west corner (row ~1~, column ~1~) facing east. This is guaranteed to not contain a gate. During every second, if Korra is not occupying the same position as a gate, then she will move forward in whatever direction she is currently facing. If she happens to be right in the place of a gate, then she will turn accordingly based on whichever direction the gate happens to be facing in that second. For example if she is facing east and she walks onto a gate with orientation /, then she will turn to face north in that second, then move to the cell north of her in the next second.

Korra will have succeeded if she manages to leave the maze. Following the above guidelines for moving, Korra would like to know the number of seconds she would spend inside the maze of gates. It is guaranteed that she will always be able to exit.

Input Specification

Line 1: The two integers ~N~ and ~M~.
Next ~N~ lines: ~M~ characters per line, depicting the initial conditions of the maze.

Output Specification

Output a single line containing a single integer – the number of seconds she spends inside the maze of airbending gates.

Sample Input

3 5
./...
...\.
././.

Sample Output

6

Explanation

The following outlines Korra's movements throughout the maze (her location and direction are represented by the characters > < ^ v):

  t = 0         t = 1         t = 2         t = 3
> / . . .     .v\ . . .     . / . . .     . \ . . .
. . . \ .     . . . / .     . v . \ .     . . . / .
. / . / .     . \ . \ .     . / . / .     . \>. \ .

  t = 4         t = 5         t = 6
. / . . .     ..\ . . .     . / . . .
. . . \ .     . . . / .     . . . \ .
. / > / .     . \ .v\ .     . / . / .
                                  v