리코셰 로봇

공장 바닥에서 최대 네 대의 로봇이 부품을 옮긴다. 바닥은 직사각형 격자이고 로봇 한 대는 칸 하나를 차지한다. 로봇에는 1번부터 4번까지 번호가 붙어 있고, 상하좌우 네 방향으로 움직인다. 한 번 움직이기 시작한 로봇은 직선으로 미끄러지다가 진행 방향의 다음 칸이 벽이거나, 바닥 바깥이거나, 다른 로봇이 있는 칸일 때만 멈춘다. 로봇은 동시에 움직이지 않는다. 한 단계에 정확히 한 대만 움직인다.

1번 로봇을 목표 칸에 올려놓는 가장 짧은 이동 순서를 구한다. 목표 칸에 닿으려면 다른 로봇을 비켜 세우거나, 1번 로봇이 부딪혀 멈추도록 다른 로봇을 미리 세워 두어야 할 수 있다.

목표 칸은 로봇을 멈추게 하지 않는다. 로봇을 멈추게 하는 것은 벽과 바닥의 가장자리, 다른 로봇뿐이다. 그래서 1번 로봇은 목표 칸을 지나쳐 미끄러지면 안 되고 목표 칸에서 이동을 끝내야 한다.

바닥 배치와 각 로봇의 시작 칸, 목표 칸이 주어지면 1번 로봇이 목표 칸에 도착하는 데 필요한 최소 이동 횟수를 구하라.

첫째 줄에 로봇의 수 $n$, 바닥의 너비 $w$와 높이 $h$, 탐색할 이동 횟수의 상한 $\ell$이 주어진다.

이어지는 $h$개 줄에는 바닥의 각 행이 정확히 $w$개의 문자로 주어진다.

• W 벽이 있는 칸
• X 하나뿐인 목표 칸
• 1, 2, 3, 4 로봇의 시작 칸
• . 빈 칸

1번 로봇이 목표 칸에 도착하는 최소 이동 횟수를 출력한다. 이동 횟수가 $\ell$ 이하인 방법이 없으면 NO SOLUTION을 출력한다.

• $1 \le n \le 4$
• $1 \le w$, $1 \le h$, $\max(w, h) \le 10$
• $1 \le \ell \le 10$