방향 미로

방향 미로는 대부분의 미로와 마찬가지로, 목표 교차로에 도달할 때까지 한 교차로에서 다음 교차로로 이동하며 통과한다. 어떤 교차로에 특정 방향에서 접근하면, 그 교차로 입구 근처의 표지판이 그 교차로에서 어느 방향으로 나갈 수 있는지 알려 준다. 나갈 수 있는 방향은 항상 좌회전, 직진, 우회전, 또는 이들의 조합이다.

그림 1은 방향 미로의 예시이다. 각 교차로는 (행, 열) 쌍으로 나타내며, 왼쪽 위가 (1, 1)이다. 그림 1에서 입구(Entrance) 교차로는 (3, 1)이고 목표(Goal) 교차로는 (3, 3)이다. 미로는 (3, 1)에서 북쪽으로 이동하며 시작한다. (3, 1)에서 (2, 1)로 걸어가면, (2, 1)의 표지판은 남쪽에서(즉 북쪽으로 이동하며) (2, 1)에 접근할 때에는 직진만 할 수 있음을 나타낸다. 직진하면 (1, 1) 방향으로 가게 된다. (1, 1)에 남쪽에서 접근할 때의 표지판은 우회전으로만 (1, 1)을 나갈 수 있음을 나타낸다. 그러면 동쪽을 향하게 되어 (1, 1)에서 (1, 2) 쪽으로 걷는다. 여기까지는 선택의 여지가 없었다. (1, 2)에서 (2, 2), (2, 3), (1, 3)으로 이동하는 동안에도 마찬가지이다. 그러나 (1, 3)에서 서쪽으로 (1, 2)를 향해 이동할 때에는 계속 직진할지 좌회전할지 선택할 수 있다. 계속 직진하면 (1, 1) 쪽으로 가고, 좌회전하면 남쪽으로 (2, 2)로 가게 된다. 이 미로의 실제 (유일한) 해답은 다음 교차로 순서를 지난다: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).

이동 중인 방향에 대한 표지판이 없는 교차로에 도달하면(예를 들어 그림 1에서 남쪽으로 이동하여 (3, 1)에 도달하는 경우), 그곳은 막다른 길이며 그 교차로 너머로는 나아갈 수 없다.

여러분은 올바른 방향 미로를 푸는 프로그램을 작성해야 한다. 미로를 푼다는 것은, 가능하다면 정해진 방향으로 입구를 떠나 목표에서 끝나는 경로를 찾는 것이다. 이 경로는 필요 이상으로 길어서는 안 된다.

입력은 하나 이상의 방향 미로로 이루어진다. 각 미로 설명의 첫 번째 줄에는 미로의 이름이 있으며, 이는 20자를 넘지 않는 영숫자 문자열이다. 다음 줄에는 순서대로 시작 행, 시작 열, 시작 방향, 목표 행, 목표 열이 하나의 공백으로 구분되어 주어진다. 미로의 최대 크기는 9 × 9이므로, 모든 행 번호와 열 번호는 1부터 9까지의 한 자리 숫자이다. 시작 방향은 N, S, E, W 중 하나이며 각각 북, 남, 동, 서를 뜻한다.

미로의 나머지 각 줄은 다음 형식을 가진다: 두 정수, 하나 이상의 문자 그룹, 그리고 종료를 뜻하는 별표(*)가 모두 하나의 공백으로 구분되어 있다. 두 정수는 어떤 교차로의 행과 열이다. 각 문자 그룹은 그 교차로에 있는 표지판 하나를 나타낸다. 그룹의 첫 문자는 N, S, E, W 중 하나로, 그 표지판이 보이는 이동 방향을 나타낸다. 예를 들어 S는 남쪽으로 이동할 때 보이는 표지판(즉 교차로의 북쪽 입구에 세워진 표지판)을 뜻한다. 이 첫 문자 뒤에는 한 개에서 세 개의 화살표 문자가 따라오며, L, F, R은 각각 좌회전, 직진, 우회전을 뜻한다.

한 미로의 교차로 목록은 첫 번째 열에 0 하나만 있는 줄로 끝난다. 그다음 줄부터 다음 미로가 시작되며, 이런 식으로 계속된다. 입력의 끝은 한 줄에 홀로 있는 단어 END이다.

각 미로에 대해, 먼저 미로의 이름을 담은 줄을 출력하고, 이어서 그 미로의 답 또는 문구 No solution possible을 담은 줄을 출력한다. 미로 이름은 1번째 열에서 시작해야 하고, 두 번째 줄은 3번째 열에서 시작해야 한다(즉 공백 두 칸으로 들여쓴다).

정해진 방향으로 입구를 떠나 목표에서 끝나는 모든 경로 중에서, 가장 짧은 경로란 지나는 교차로의 수가 가장 적은 경로를 뜻한다(입구와 목표를 포함하며, 같은 교차로를 여러 번 지나면 지날 때마다 센다). 미로를 풀 수 있으면 이 가장 짧은 경로가 지나는 교차로의 개수를 출력하고, 그렇지 않으면 No solution possible을 출력한다.