열쇠 미로 탈출

미로에 갇혔습니다. 출구를 찾아 탈출해야 합니다.

미로는 정사각형 칸으로 이루어진 2차원 격자입니다. 각 칸은 빈 칸이거나 벽으로 막혀 있습니다. 일부 빈 칸에는 문이나 열쇠가 놓여 있습니다. 열쇠와 문은 파랑, 노랑, 빨강, 초록 네 가지 색이 있으며, 열쇠는 같은 색 문만 열 수 있습니다.

상하좌우로 인접한 빈 칸으로만 이동할 수 있고, 대각선 이동은 허용되지 않습니다. 벽을 통과할 수 없고 격자 밖으로 나갈 수도 없습니다. 문이 있는 칸에는 그 문과 같은 색 열쇠가 놓인 칸을 이미 밟아 열쇠를 얻은 경우에만 들어갈 수 있습니다. 한 번 밟은 열쇠는 그 미로가 끝날 때까지 계속 가지게 됩니다.

입력은 여러 개의 미로로 이루어집니다.

각 미로는 두 정수 R과 C (1 ≤ R, C ≤ 100)가 적힌 줄로 시작합니다. R은 행의 수, C는 열의 수입니다. 이어지는 R개의 줄에는 각각 정확히 C개의 문자가 있으며 미로를 나타냅니다. 각 문자는 다음 중 하나입니다.

한 미로에 출구가 여러 개일 수도, 하나도 없을 수도 있습니다. 같은 색의 문이나 열쇠가 여러 개 있을 수 있고, 대응하는 문이 없는 열쇠나 대응하는 열쇠가 없는 문이 있을 수도 있습니다. 시작 위치 *는 모든 미로에 정확히 한 번 나타납니다.

각 미로 뒤에는 빈 줄이 하나 있습니다. 입력은 R과 C 자리에 0 0이 적힌 줄로 끝나며, 이 줄은 미로가 아닙니다.

각 미로마다 한 줄을 출력합니다.

출구에 도달할 수 있으면 Escape possible in S steps.를 출력합니다. 여기서 S는 어떤 출구든 도달하는 데 필요한 최소 이동 횟수입니다.

출구에 도달할 수 없으면 대신 The poor student is trapped!를 출력합니다.

한 번의 이동은 인접한 두 칸 사이의 이동을 뜻합니다. 열쇠를 줍거나 문을 여는 것은 이동으로 세지 않습니다.