19537번 - 전투 시뮬레이션

당신은 $H \times W$ 크기의 $2$차원 격자 맵에서 두 세력이 전투를 벌이는 시뮬레이션 게임을 개발하고 있다. 

격자의 각 칸은 $y$좌표와 $x$좌표의 쌍 $\left(y, x\right)$로 표현할 수 있다. 첫 번째 줄에 있는 칸들은 왼쪽부터 순서대로 $\left(0, 0\right), \left(0, 1\right), \cdots, \left(0, W-1\right)$로 표현하며, 두 번째 줄의 칸들은 $\left(1, 0\right), \left(1, 1\right), \cdots, \left(1, W-1\right)$로 표현한다. 같은 방법으로 $H$번째 줄까지의 모든 칸들을 좌표로 표현한다. 어떤 칸의 위, 아래, 왼쪽, 오른쪽 칸들은 그 칸에 ‘인접한’ 칸이라고 한다.

맵은 다양한 지형으로 이루어져 있고 각 지형은 정해진 ‘험준도’ 수치를 가진다. 또, 맵에는 여러 유닛이 서로 겹치지 않게 배치되어 있으며, 각 유닛은 전투 중인 두 세력 중 한 세력에 속한다. 각 유닛은 맵 밖으로 벗어나지 않는 한 위치한 곳으로부터 상하좌우로 인접한 칸으로 이동할 수 있다. 이동 시에는 해당 칸의 지형이 가진 험준도만큼의 스태미나를 소모하게 된다. 일부 지형은 너무 험준하여 이동이 불가능할 수도 있다. 세력이 다른 두 유닛이 인접해 있다면 그 둘은 교전 상태이다.

모든 유닛은 전투식량을 든든하게 챙겨 먹고 나왔기 때문에 무한한 스태미나를 가지고 있다. 다만 각 유닛은 한 번의 약진에 최대로 소모할 수 있는 스태미나 총량이 제한되어 있으며, 이를 유닛의 ‘이동력’이라고 한다. 약진이란 전투 중인 유닛이 비교적 가까운 목표지점까지 빠르게 달려 단숨에 이동하는 전술 행동으로서 하나 이상의 칸을 거쳐 이동하는 것이다. 약진은 목표지점에 다른 유닛이 없어야만 가능하다. 약진 중에 같은 세력의 유닛을 만났다면 통과하여 지나갈 수 있으나, 다른 세력의 유닛을 만났다면 그 유닛과 상하좌우로 인접하게 되는 순간 교전이 벌어지기 때문에 그 자리에 멈춰야만 한다. 하지만, 선택된 유닛이 이미 교전 상태였다면 약진하여 교전에서 벗어날 수 있다.

당신은 게임에 버그가 있는지 테스트하기 위해서 자동으로 임의의 유닛을 선택하여 약진 명령을 내리는 봇을 만들었다. 이 봇은 수행이 불가능한 약진 명령을 내리기도 한다. 목표 지점에 다른 유닛이 있거나, 목표 지점이 이동 불가 지형이거나, 이동력의 한계로 인해 목표 지점에 도달하는 경로가 존재하지 않는 경우, 그 명령은 수행 불가능하다. 게임에 버그가 없다면 이러한 명령은 무시되어야 한다.

이제 버그가 있는지 없는지 확인할 시간이다. 봇이 내린 명령들이 시간 순으로 주어졌을 때, 모든 명령이 순차적으로 처리된 후 각 유닛이 위치한 좌표를 출력하는 프로그램을 작성하시오.

첫 번째 줄에 지형의 종류 수 $N$, 맵의 세로 길이 $H$, 맵의 가로 길이 $W$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 9$, $2 \leq H,W \leq 500$)

이어서 $H$개의 줄에 걸쳐 왼쪽부터 차례대로 각 칸의 지형 번호를 의미하는 $W$개의 정수가 공백으로 구분되어 주어지며, 각 수는 $1$ 이상 $N$ 이하이다.

다음 줄에 $N$개의 정수 $r_1, r_2, \cdots, r_N$ ($-1 \leq r_i \leq 4$, $r_i \neq 0$)이 공백으로 구분되어 주어진다. $r_i$가 $-1$이라면 $i$번째 지형이 너무 험준하여 진입할 수 없음을 의미하며, 이외의 경우에는 $r_i$는 $i$번째 지형의 험준도를 의미한다.

다음 줄에 유닛의 수 $M$이 주어진다. ($1 \leq M \leq H \times W / 4$)

이어서 $M$개의 줄에 걸쳐 $1$번 유닛부터 차례로 각 유닛의 이동력, 세력, 유닛이 있는 칸의 $y$좌표, 유닛이 있는 칸의 $x$좌표 정보를 의미하는 네 개의 정수 $m$, $t$, $a$, $b$가 공백으로 구분되어 주어진다. ($1 \leq m \leq 20$, $0 \leq t \leq 1$, $0 \leq a < H$, $0 \leq b < W$)

각 칸에는 최대 하나의 유닛이 배치되며, 진입 불가능한 지형의 칸에는 유닛이 배치되지 않는다.

다음 줄에 약진 명령의 개수 $K$ ($1 \leq K \leq 10\ 000$)가 주어진다.

이어서 $K$개의 줄에 걸쳐 약진 명령을 의미하는 세 정수 $u$, $a$, $b$가 공백으로 구분되어 주어진다. ($1 \leq u \leq M$, $0 \leq a < H$, $0 \leq b < W$) 이는 $u$번 유닛을 $\left(a, b\right)$로 약진시키는 명령이다.

$M$개의 줄에 걸쳐 모든 약진 명령이 처리된 후의 유닛의 위치를 출력한다. $i$번 유닛이 $\left(a_i, b_i\right)$에 위치할 경우 $i$번째 줄에 두 정수 $a_i$, $b_i$를 공백으로 구분하여 출력한다.

첫 번째 약진 명령의 경우, 적대 세력 유닛을 고려하지 않는다면 $\left(2, 0\right)$ → $\left(2, 1\right)$ → $\left(2, 2\right)$ → $\left(2, 3\right)$ → $\left(1, 3\right)$과 같은 경로로 이동하여 도달할 수 있다. 하지만 $\left(3, 3\right)$에 위치한 적대 세력 유닛으로 인해 $\left(2, 3\right)$에서 교전이 발생하므로 $\left(1, 3\right)$에는 도달할 수 없고, 교전이 발생하지 않도록 우회해서 이동할 수 있는 경로가 없으므로 마찬가지로 도달할 수 없다. 따라서 이 명령은 수행 불가능하므로 무시된다.

두 번째 약진 명령은 목표 위치가 이동 불가 지형이기에 수행 불가능하므로 무시된다.

세 번째 약진 명령은 $\left(2, 0\right)$ → $\left(3, 0\right)$ → $\left(4, 0\right)$ → $\left(4, 1\right)$ → $\left(4, 2\right)$ → $\left(4, 3\right)$의 경로로 움직이면 $7$의 스태미나를 소모하여 이동할 수 있다. 이는 유닛의 이동력보다 크지 않은 값이므로 수행할 수 있는 명령이다.

따라서 모든 명령이 처리된 후 $1$번 유닛은 마지막 명령에 의해 $\left(4, 3\right)$에 위치하고 $2$번 유닛은 초기 위치에 그대로 위치히게 된다.