A board solitaire game (2) P51344

You have an n × m board. Some positions have objects that, when pressed, start moving in the direction painted on them, until they leave the board, or until they reach another object and stop just before crashing. The painted directions are ‘>’ ‍for rightwards, ‘<’ for leftwards, ‘^’ for upwards and ‘v’ for downwards. The goal of the game is to empty the board minimizing the number of times that we press the objects.

Input

Input consists of several cases, each with n and m, followed by n lines with m characters each. Periods indicate empty cells. Assume 1 ≤ n · m ≤ 20, that there is at least one object on the board, and that the game is solvable.

Be aware that the ‘^’ char that Latex uses in the pdf of this statement is not an ASCII char. Use the html version of the statement to copy and paste the sample.

Output

For every game, print the minimum cost to solve it.

Hint

The expected solution is neither a BFS nor a backtracking.