402920: GYM100947 H Phobia

Sally has a phobia of cockroaches. Every night she is having the same horrible nightmare! Where she is standing alone in a big maze surrounded by millions and millions of cockroaches. She wakes up horrified and screaming when she sees a huge cockroach standing on her foot. After many sleepless nights like that one, she finally decided to ask you for help.

Since you have some experience with psychology (after all you are a programmer, right?) you tell her that the best way to cure her phobia is to fight it. She must be strong and fight these stinky little insects. After many argument she agrees with you and decides that she must overcome her fears. To do so she must reach for her sandals (you know, she needs a weapon for this great battle). Sally marked her sandals with a big red X sign to make sure they are clearly noticeable.

Here comes your job! You thought that you should write a program to help her train for this battle. Given the maze information, your program should tell her whether if she could reach her sandals without being touched by any cockroach.

The maze is an N × M rectangular grid, each cell of this grid is either empty or a wall or a hole. Cockroaches emerge from these holes and spread in all directions. Sally and Cockroaches cannot pass through walls, in other words Sally can only move to an empty cell, and cockroaches can only occupy an empty cell.

Formally, at time t if cell (i, j) is occupied by cockroaches then in time t + 1 cells (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1) as well as cell (i, j) will be occupied by cockroaches if the respective cells are empty and are inside the borders of the maze.

In one second, Sally can move to an adjacent empty cell. Formally if at time t Sally is at cell (i, j), then in time t + 1 she can move to one of these cells: (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1) if the respective cells are empty and are inside the borders of the maze.

One empty cell contains Sally starting position, and One other empty cell Contains her Sandals. Sally's goal is to reach her sandals without touching any cockroach. Sally touches a cockroach when Sally's current position is occupied by cockroaches.

The first line will be the number of test cases T.

Each test case contains two integers N and M (1 ≤ N, M ≤ 100) followed by N × M grid that represents the maze where:

'S' : sally's starting position.

'X' : Sally's sandals position.

'#' : a Wall.

'*' : a hole.

'.' : an empty cell.

For each test case print "yes" if Sally can exit from the maze without touching any cockroach or "no" otherwise.

2
5 5
S..#*
...#.
...##
.....
....X
5 5
S..#*
...#.
...#.
.....
....X

yes
no