In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of April 14th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]
In this problem you should submit a complete program with the main function, reading with functions such as scanf and printing with functions such as printf.
Rachel Green is facing a serious crisis—there’s a HUGE designer sale, and she HAS to get to the store before someone else buys the last perfect outfit. (Priorities, people!). The only problem? She’s lost. Again.
This mall is basically a giant maze, and she has no idea if she can even reach the store. (Seriously, who designs these places?!).
The mall layout is represented as a 2D grid where 'R' is Rachel's starting position, 'S' is the store she wants to reach, '.' is a walkable path and '#' is a wall. Rachel can move up, down, left and right (but not diagonally - she he is in heels, after all).
Your task is to Help Rachel figure out if there's a way to get from where she is to the store. There are several mall layouts, and for each of them you need to find if there is a path from 'R' to 'S' only using walkable cells ('.').
On the first line there is an integer N indicating the amount of cases to consider.
Each case starts with two numbers R and C indicating respectively the number of rows and columns of the petri dish. The R lines follow, each one with C characters, indicating the contents of each position: 'R' for the position of Rachel, 'S' for the store, '.' for a walkable path and '#' for a wall. There will always be exactly one position with 'R' and one position with 'S' in the layout of each mall.
The output should have N lines, one for each case, containing "yes" if Rachel can reach the store and "no" if there is no possible path.
The following limits are guaranteed in all the test cases that will be given to your program:
1 ≤ N ≤ 20 | Number of test cases | |
1 ≤ R, C ≤ 100 | Dimensions of the matrix |
Example Input | Example Output |
2 5 10 ..#....... ###...#... ..#...#..S .R#...#### ......#... 4 4 R..# ..#. .#.. #..S |
yes no |
On the first case Rachel can reach all the positions in green, which include the store (hence, the answer is "yes"):
..#....... ###...#... ..#...#..S .R#...#### ......#...On the second case Rachel can reach all the positions in green, which don't include the store (hence, the answer is "no"):
R..# ..#. .#.. #..S