Problemas
M*N의 격자로 구성되어 있는 미로 안에 로봇이 갇혀있다. 미로의 몇 개의 공간은 비어 있으며 몇 개의 공간은 벽으로 막혀있어서 로봇은 벽안으로 들어갈 수가 없다. 하지만 로봇은 드릴을 이용하여 벽을 깨뜨릴 수 있다. 미로의 외벽은 너무 튼튼하여 로봇은 미로 밖으로는 나갈 수 없다.
여러분은 맵과 로봇의 처음 위치가 주어질 때 로봇이 목적지까지 어떻게 이동해야 할지 명령을 입력해야 한다. 로봇은 수직과 수평 방향의 빈 셀로만 움직일 수 있다. 드릴을 사용하여 벽이 있는 셀을 빈 셀로 만들 수 있는 데 이 경우 1의 에너지를 소비한다. 에너지는 제한적이므로 잘 사용해야 한다. 에너지가 0이 되면 벽을 깨뜨릴 수 없다. 과연 여러분은 로봇을 구할 수 있을까?
Entrada
입력은 몇 개의 테스트 케이스로 주어진다.
다음 M개의 줄에 걸쳐 미로의 상태가 공백으로 구분하여 주어지는데 'S' 는 시작위치를 'T'는 도착위치를 나타내며, 빈 공간은 '.'으로 막혀있는 공간은 '*'으로 표시되어 주어진다.
첫 줄에 테스트 케이스의 수 T( 1≤T≤20 )이 주어진다. 각 테스트 케이스의 첫 줄에는 에너지의 양이 정수 K(K≥0)가 주어진다.
다음 줄에 격자의 크기를 나타내는 두 수 1≤M≤500, 1≤N≤500 이 공백으로 구분하여 주어진다.
Salida
각 테스트 케이스에 대하여 K에너지를 사용하여 가능한 경우에는 'y'를 불가능한 경우에는 'n'을 한 줄에 출력한다.
Ejemplo
2
4
2 2
S .
. T
0
2 2
S *
* T
y
n
Debes iniciar sesión para escribir código.