Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.
The maze type is shown in following figure:
S$###
$$#$$
$$$##
##$$F
it consists of S (starting point), #(walls), $(road) and F (final point).
In above case, it needs 7 steps from S to F as following figure,
S$###
$$#$$
$$$##
##$$F
and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.
If there is no way from S to F, then print -1.
Hint: You can use the following code to read the input.
#include<stdio.h>
int main(){
...
while(--N>=0) {
scanf("%d %d", &R, &C);
for(i=0; i<R; i++)
for(j=0; j<C; j++) {
scanf(" %c", &maze[i][j]);
...
}
}
...
return 0;
}
The first line has an integer N(1<=N<=10^6), which means the number of test cases.
For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.
The following R lines, each containing C characters, specify the elements of the maze.
Print out the least steps for each case, and there is a new line character at the end of each line.