Heading Home

It's another ordinary day in quarantine. As diligent programmers, you've spent your entire day hunting down a sneaky bug, and you decide to take an afternoon stroll to think more clearly. However, absorbed in your thoughts, you lose track of time. It's 9 o'clock, and the curfew is just starting. You know that at exactly 9, a police officer starts patrolling from the police station, and if they see you, they will impose a hefty fine. You want to get home without getting fined. It's your chance to use the algorithmic knowledge you've gained during all this time in quarantine!

The map of your town is represented by a grid with dimensions N ~\times~ M. Each square on the grid can be either a road or a building. Additionally, your initial position, the position of the police station, and the position of your house are known.

You need to plan a pre-determined route starting from your initial position, ending at your house, and consisting of a sequence of moves. In each move, you can only advance (horizontally or vertically) to a neighboring square that is not a building. At the same time, the police officer can move in a similar way or remain stationary. Your movement, along with the reaction of the police officer, completes in one minute.

After each minute, the following can happen:

• If you are in the police officer's line of sight, meaning on the same row (horizontally) or column (vertically) without any building in between, you will receive a fine.
• If you haven't received a fine and are at your house, you safely enter.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the description of your town and decides whether there is a pre-determined safe route to your house, regardless of how the police officer moves.

Input File:

The input file named wayhome.in is a text file with the following structure. The first line contains an integer T, the number of the problem's scenarios. Then, T scenarios follow, each with the following structure.

The first line contains two integers N and M, the dimensions of the town. Each of the next N lines contains M characters, describing the corresponding squares. Each character can be either . (road), # (building), Y (your position), P (police officer's position), or H (your house position). Assume that each character from Y, P, and H will appear exactly once and can be used as a road for movement.

Output File:

The output file named wayhome.out is a text file with the following structure. It consists of T lines, each corresponding to the answer of a scenario and containing exactly one string: YES if there is a safe route to your house, and NO otherwise.

Example of input - output file:

STDIN (wayhome.in)

3
5 7
Y.....P
..#....
..#####
.......
...H...
5 7
Y....P.
..#....
..#####
.......
...H...
2 3
.YH
P##

STDOUT (wayhome.out)

YES
ΝΟ
ΝΟ

Explanation of Scenario 1: A safe route to your house is as follows: down, down, down, right, right, right, down. Note that the police officer cannot fine you at the beginning since the curfew starts from the first minute after 9.

Explanation of Scenario 3: Note that to enter your house safely, the police officer should not see you.

Constraints:

• 1 ~\le~ T ~\le~ 12
• 1 ~\le~ N, M ~\le~ 700
• For test cases with a total value of 17%, the map will have no buildings.
• For test cases with a total value of 42%, 1 ~\le~ N, M ~\le~ 200.

Attention! Be sure to read the input and print the output efficiently, especially if you are programming in C++ or Java.

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.