In the village of hakka's, there are lots of big big mazes.
It is said that the delicious hakka mochi (麻糬) is hidden in one of the secret mazes.
You, a poor programmer, working for hakkas without getting any paid,
want to find out the secret, and change the job to selling mochi,
since being a programmer is too tired, and may die overworked.
So, one day, you sneaked into the village head's house, and stole all the mazes' maps out.
You have got T maps, where
each map shows that the maze is N*M grids big,
and starts from (1,1) (the left top corner), and the mochi is at (N,M) (the right bottom corner),
and a '#' on the map represents a wall,
and a '*' on the map represents that you can walk through that grid,
and the 'A', 'B' and 'C' represent 3 different types of traps (陷阱) on the map.
Walking in a hakka's maze, starting from the starting point (1,1),
if you are standing on a road,
you can go to the up, right, left, or the bottom grid near you,
but you cannot be on a wall,
and there are 3 kinds of traps on the map, where
at the first step, for example during (1,1)->(1,2), the type A traps will be on, and the B, C traps will be off,
at the second step, the type B traps will be on, and the A, C traps will be off,
at the third step, the type C traps will be on, and the A, B traps will be off,
at the fourth step, the type A traps will be on, and the B, C traps will be off,
and repeatedly.
You want to make sure if it is possible to walk from the starting point (1, 1) to the ending point (N, M) of each map,
so you won't waste time finding the mochi.
ouo.
Example 1:
If the input is:
1
1 3
*A*
The output should be 'No' (without quotes), since if you move right, the 'A' trap will be on, so you cannot move.
Example 2:
If the input is:
1
1 6
**BCA*
The output should be 'Yes', since you can move (right, left, right, right, right, right, right) and get to the end point,
but you cannot just go right straight since you will step on the B trap.
Hint:
As shown in the above Example 2, a grid should be allowed to be visited more than once, in order to check if we can obtain a walking sequence that fits the trap on-off pattern.
For this, we can use a 3D array visited[N][M][3] to record if a grid (x,y) has been previously visited in a different trap setting as follows:
In this way, we allow (x,y) to be visited more than once while avoiding TLE.
The first line contains an integer T,
representing the number of maps.
Starting from the second line, there are T maps, in each of which,
the first line contains 2 numbers N, M, indicating that the maze is N*M big,
then each of the following N lines contains M characters, where
a character '#' represents that the grid is a wall,
a character '*' represents that the grid is a road, and
the characters 'A', 'B', 'C', represent 3 different types of traps.
It is guaranteed that:
for all test cases: 1 <= T <= 10, 1 <= N, M <= 1000,
for test case 1, without traps, 1 <= N, M <= 10,
for test case 2, without traps, 1 <= N, M <= 800,
for test case 3, without traps, 2 <= N, M <= 200,
for test case 4, without traps, 2 <= N, M <= 1000,
for test case 5, with traps, N = 1, 1 <= M <= 300,
for test case 6, with traps, 1 <= N, M <= 800.
Output T lines, in each of which
if it is possible to walk from the starting point to the ending point in the corresponding maze,
output "Yes", otherwise, output "No". (Without quotes)