Rook in the Maze#1746
A rook is a chess piece that can move any number of cells horizontally or vertically in one move. However, it cannot "jump over" pieces that are blocking its path.
Vasya has recently created a peculiar maze on a chessboard—he placed pawns (the weakest chess pieces) on some of the cells. Now he wants to know the minimum number of moves required for the rook to get from one cell to another.
He has been pondering this question for several days but hasn't been able to find the answer. So he turned to you for help. Write a program that finds the answer to Vasya's question.
The first line of the input file contains two positive integers: and (1 \le n, m \le 500) — the dimensions of the maze.
Each of the next lines contains characters. The -th character of the -th of these lines corresponds to the cell with coordinates . It is "." (a dot) if the cell is empty, P if it is occupied by a pawn, S if it is the starting cell for the rook, or F if it is the target cell.
Output the minimum number of moves required for the rook to get from the starting cell to the target cell. If the target cell is not reachable from the starting cell, output -1.
Example 1