주사위 굴리기
시간 제한5초메모리 제한512 MB
주사위를 시작 칸에서 목표 칸까지 굴릴 때 윗면 문자열을 순서대로 이어 붙인 결과 중 사전순으로 가장 작은 값을 구합니다. 경로가 없으면 no, 무한히 작아지면 infinite를 출력합니다.
문제
직사각형 지도 위에 주사위가 놓여 있다. 지도는 H행 W열의 격자로 이루어져 있고, 시작 칸과 목표 칸이 하나씩 표시되어 있다. 주사위는 처음에 시작 칸에 있으며, 목표 칸에 도달할 때까지 굴린다.
주사위를 굴린다는 것은 지도에 닿아 있는 밑면의 모서리 네 개 중 하나를 골라, 그 모서리를 지도에서 떼지 않은 채 주사위를 쓰러뜨리는 것이다. 따라서 주사위는 네 방향으로 움직일 수 있다. 각 칸의 지시 문자에 따라 움직일 수 있는 방향이 제한된다.
- '+': 모든 방향
- '|': 위아래 방향만
- '-': 좌우 방향만
- '<': 왼쪽으로만
- '>': 오른쪽으로만
- '^': 위쪽으로만
- 'v': 아래쪽으로만
- '.': 굴릴 수 없음
지시 문자와 관계없이 주사위를 지도 바깥으로 굴릴 수는 없다.
주사위의 각 면에는 문자열이 적혀 있다. 시작 칸에서 목표 칸까지 굴리는 동안 칸마다 윗면의 문자열을 기록하고, 이를 순서대로 이어 붙인다. 목표 칸에 도달하는 경로는 여러 개일 수 있으므로, 이어 붙인 문자열이 사전순으로 가장 작은 것을 출력한다. 목표 칸에 도달하는 경로가 없는 경우도 있고, 사전순 최소 문자열을 끝없이 길게 만들 수 있는 경우도 있다.
처음에는 1번 면이 위를 향하고, 1번 면의 윗변이 지도의 맨 윗행을 향한다. 그림 1은 주사위의 전개도이다.
그림 1. 주사위의 전개도
입력
첫 줄에 H와 W가 주어진다 (1 ≤ H ≤ 12, 1 ≤ W ≤ 12). 이어서 H개의 줄에 지도가 주어지며, i번째 줄의 j번째 문자는 i행 j열 칸의 지시 문자이다.
다음 6개의 줄에는 주사위 각 면에 적힌 문자열 T1부터 T6이 주어진다. 각 문자열은 비어 있지 않고, 길이는 12 이하이며, 대문자 알파벳과 숫자로만 이루어져 있다. 면의 번호는 그림 1과 같다.
마지막 두 줄에는 정수 두 개씩 주어진다. 첫 줄은 시작 칸의 행 번호와 열 번호 RS CS이고, 다음 줄은 목표 칸의 행 번호와 열 번호 RD CD이다. 시작 칸과 목표 칸은 항상 다르다.
H W
C11 ... C1W
...
CH1 ... CHW
T1
...
T6
RS CS
RD CD
출력
사전순으로 가장 작은 문자열을 한 줄에 출력한다. 목표 칸에 도달하는 경로가 없으면 no를 출력한다. 사전순 최소 문자열을 끝없이 길게 만들 수 있으면 infinite를 출력한다.