Escape the Maze with a Drill

Interview

Time limit1sMemory limit128 MB

Summary

Decide whether a robot can reach the target on a grid by drilling through at most k walls.

Level: Medium4 of 10
Topics: Shortest path, BFS, Graph, Matrix
Solved: No attempts yet

Problem

A robot is trapped in a maze shaped as an $M \times N$ grid. Each cell is either empty or a wall. The robot cannot step onto a wall directly, and it can never leave the maze because the outer boundary is solid. The robot does carry a drill, however: spending $1$ unit of energy turns one wall cell into an empty cell, after which the robot may enter it.

The robot starts at a given cell and wants to reach a destination cell. In one step it moves to a cell that is horizontally or vertically adjacent. Entering an empty cell is free, but entering a wall cell requires first drilling that wall, which costs $1$ unit of energy. The robot has a limited amount of stored energy.

Given the map of the maze and the amount of stored energy, decide whether the robot can reach the destination.

Input

The first line contains an integer $T$ ( $1 \le T \le 20$ ), the number of test cases.

Each test case is given as follows. The first line contains an integer $k$ ( $k \ge 0$ ), the amount of energy stored in the robot. The next line contains two integers $M$ and $N$ ( $1 \le M \le 500$ , $1 \le N \le 500$ ), the number of rows and columns of the maze. Each of the following $M$ lines contains exactly $N$ characters describing one row of the maze. The character * is a wall and . is an empty cell. S marks the robot start and T marks the destination. Every symbol on a maze row is separated from the next by at least one whitespace character.

Output

For each test case, print a single line containing y if the robot can reach the destination while spending at most $k$ units of energy, or n otherwise.

Examples2

Example 1
Input
```
2
4
2 2
S .
. T
0
2 2
S *
* T
```
Expected output
```
y
n
```

Example 2

Input

2
1
5 5
S . . . .
. . . . .
* * * * *
. . . . .
. . . . T
0
5 5
S . . . .
. . . . .
* * * * *
. . . . .
. . . . T

Expected output

y
n