9040번 - Maze 다국어채점 준비 중

문제

There is a robot trapped in a maze. The maze is an M * N grid. Some of the cells are empty, while others are occupied by the wall. Of course the robot can't move into the wall, but the robot can break wall by drills. The robot can’t move outside the maze because the maze boundary is very hard. Now you have a map of the maze and initial position of the robot. You need to send some instructions, telling the robot how to reach its destination. The robot can move to horizontally or vertically adjacent empty grid cell. Using a unit of energy, the equipped drill can change a wall cell into an empty cell. The charged energy is limited. Can you rescue the robot from the maze?

입력

The input contains several test cases. The first line of the input contains an integer number 1 ≤ T ≤ 20 indicating the number of test cases. In each test case, the first line is an integer k ≥ 0 indicating the amount of energy charged to the robot. The second line is two integers 1 ≤ M ≤ 500 and 1 ≤ N ≤ 500 indicating the size of maze. Following M lines contains the information of the maze. Each line contains exactly N characters. ‘*’ and ‘.’ indicate a wall and an empty area respectively. ‘S’ and ‘T’ indicates the initial position of the robot and the destination, respectively. All symbols are separated by at least one whitespace character.

출력

Output one line containing ‘y’ or ‘n’ for each test case, indicating whether the robot can go to the destination using less than or equal to k units of energy.

제한

힌트