2차원 평면상의 격자 모양 지도에서 주어진 물체가 목적지로 가는 최단 경로는 다익스트라 혹은 A* 알고리즘을 사용하여 계산할 수 있다. 그런데 실시간 전략 시뮬레이션 게임의 경우처럼, 여러 개의 유닛들이 동시에 움직이고 두 개 이상의 유닛이 동시에 한 칸에 함께 머무를 수 없다면 유닛들이 장애물의 역할을 하기 때문에 위의 알고리즘을 단순히 적용하여 계산하기는 어렵다.
아래와 같은 조건에서 모든 유닛을 해당 목적지까지 빠르게 이동하는 프로그램을 작성해 보자.
각 유닛에는 하나의 색이 배정되어 있다. 같은 색을 가진 여러 개의 유닛이 존재할 수 있고, 각 색마다 그 색을 가진 유닛 수만큼 목적지가 지정된다.
유닛에 배정되는 색의 가짓수는 최대 2개이다.
각 유닛은 시뮬레이션의 매 턴마다 상하좌우 중 하나의 방향으로 한 칸씩 한번만 이동하거나, 아니면 이동하지 않을 수 있다.
각 유닛은 턴의 시작 시점에 비어있는 칸으로만 이동할 수 있다. 따라서, 각 유닛은 옆 칸에 위치한 유닛이 다른 칸으로 이동하더라도 그 턴에서는 그 칸으로 이동할 수 없다.
매 턴마다 이동이 결정된 유닛들은 동시에 이동하고 해당 턴이 끝난다.
두 개 이상의 유닛이 동시에 한 칸에 머무를 수 없다. 따라서, 시뮬레이션의 시작 시점에 모든 유닛은 서로 다른 칸에 주어지며, 두개 이상의 유닛이 동시에 같은 칸으로 이동할 수 없다.
지도에서 장애물인 벽을 제외한 공간은 모두 서로 연결되어 있고, 유닛은 지도 밖으로 나갈 수 없다.
모든 턴을 마쳤을 때 유닛이 자신에게 배정된 색의 목적지들 가운데 하나에 위치할 경우에 그 유닛은 목적지에 도착한 것으로 정한다.
입력 형식
첫 줄에 지도의 세로 크기 H와 가로 크기 W가 주어진다. (1≤H≤100, 1≤W≤100)
두번째 줄부터 H개의 줄에 걸쳐, 각 줄마다 W개의 글자로 구성된 지도가 입력된다. 지도에 있는 모든 글자는 #, ., A, B, a, b 중 하나이다.
지도를 읽는 규칙은 다음과 같다.
# 은 장애물인 벽이다. 유닛은 벽으로 이동해 들어갈 수 없다.
. 은 빈 공간이다. 유닛은 빈 공간으로 이동해 들어갈 수 있다.
A 와 같이 알파벳 대문자는 그 대문자 색의 유닛 하나가 주어진 위치이다. 전체 유닛의 개수는 100이하이다.
a 와 같이 알파벳 소문자는 그 알파벳의 대문자 색의 유닛 하나가 도착해야 할 목적지이다. 목적지는 유닛의 이동에 대하여는 빈 공간과 같이 이동해 들어가거나 나올 수 있다.
모든 테스트케이스에 대해, 입력 데이터가 어떤 식으로 구성되어 있는지 추상적으로 보여주는 그림 파일을 제공한다. 즉, 입력 데이터가 정확히 그림과 일치하지 않을 수 있다. 그림 파일은 다음과 같은 형식을 따른다.