Lecette and her friends Fox and Rabbit are going to explore a strange maze. The maze is rectangle-shaped. The following types of cells exist in the maze:
※'#' - Wall. They cannot enter these cells.
※'.' - Empty cell. They can walk freely into these cells.
※'L', 'F' or 'R' - Empty cell with Entrance. They can walk freely into these cells.
To enter the maze, Lecette chooses a cell marked as 'L' randomly and uniformly. Fox does the same with a cell marked as 'F', and Rabbit does the same with a cell marked as 'R'. They will each warp to the chosen cell. Then, they decide on a meeting cell such that the total walking distance from the entrances to the meeting cell is minimized. When walking, they can only move in the four cardinal directions. They cannot move diagonally. The walking distance to a neighboring cell is 1.
Calculate the expected total walking distance in the form "X/Y" (quotes for clarity), where X and Y are positive integers with no common factor greater than 1.
The first line of input containing an integer T denoting the number of test cases.
For each test case, the first line containing two integer m,n denoting the number of rows and columns of the maze. Following m lines containing n charcter descript the maze.
1<= m,n <= 50
maze will contain between 1 and 20 'F's, inclusive.
maze will contain between 1 and 20 'R's, inclusive.
For each test case, you must print a line X/Y. In case there is a non-zero probability that they cannot meet, you should print 0/1.
3 5 9 ######### ####F#### ##L...R## ####L#### ######### 2 2 LR RF 6 8 ..F.#... L.F.#..L ..F.#... .R.#..L. ...#.... ..R#.L..
9/2 2/1 0/1
Migrated from old NTUJ.
topcoder SRM 515
| No. | Testdata Range | Score |
|---|