미로 탈출 명령어 timer 1s memory 16MB

N\times M격자 미로가 주어집니다. 당신은 미로의 (x,y)에서 출발해 (r,c)로 이동해서 탈출해야 합니다.

단, 미로를 탈출하는 조건이 세 가지 있습니다.

1. 격자의 바깥으로는 나갈 수 없습니다.

2. (x,y)에서 (r,c)까지 이동하는 거리가 총 k여야 합니다. 이때, (x, y)와 (r,c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다.

3. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다.

이동 경로는 다음과 같이 문자열로 바꿀 수 있습니다.

• l: 왼쪽으로 한 칸 이동

• r: 오른쪽으로 한 칸 이동

• u: 위쪽으로 한 칸 이동

• d: 아래쪽으로 한 칸 이동

예를 들어, 왼쪽으로 한 칸, 위로 한 칸, 왼쪽으로 한 칸 움직였다면, 문자열 "lul"로 나타낼 수 있습니다.

미로에서는 인접한 상, 하, 좌, 우 격자로 한 칸씩 이동할 수 있습니다.

예를 들어 다음과 같이 3\times 4격자가 있다고 가정해 보겠습니다.

....
..S.
E...

미로의 좌측 상단은 (1,1)이고 우측 하단은 (3,4)입니다. .은 빈 공간, S는 출발 지점, E는 탈출 지점입니다.

탈출까지 이동해야 하는 거리 K가 5라면 다음과 같은 경로로 탈출할 수 있습니다.

1. lldud

2. ulldd

3. rdlll

4. dllrl

5. dllud

6. ...

이때 dllrl보다 사전 순으로 빠른 경로로 탈출할 수는 없습니다.

• 1 ≤ N (= 미로의 세로 길이) ≤ 100

• 1 ≤ M (= 미로의 가로 길이) ≤ 100

• 1 ≤ X ≤ N

• 1 ≤ Y ≤ M

• 1 ≤ R ≤ N

• 1 ≤ C ≤ M

• (X, Y) ≠ (R, C)

• 1 ≤ K ≤ 10,000