14744번 - God Game

태영이는 게임 중독이다. 그는 Legend of League라는 게임에 빠져 공부도 제대로 하지 않고 나날을 게임과 함께 보내고 있었다. 그런 태영이를 한심하게 생각했던 준형이는 본인이 직접 갓게임을 만들어 태영이를 Legend of League에서 탈출시키기로 마음먹었다.

준형이가 만든 게임은 다음과 같다. 게임은, 좌표평면의 1사분면에 있고 한 꼭짓점이 원점인 $N\times M$ 크기의 직사각형에서 이루어진다. $N$과 $M$은 모두 정수이다. 게임의 목표는 시간 $t=0$에 $(startX, startY)$에서 시작해 $(endX, endY)$로 옮기는 것이다. 이 좌표들은 모두 정수 좌표들이다. 태영이는 각 정수 시간 $t$에 대해 다음 두 가지 행동 중 하나를 할 수 있다.

1. 공을 1초동안 제자리에 가만히 놔둔다.
2. 현재 공의 위치가 $(x, y)$라면, 초당 1칸의 속도로 1초 동안 $(x+1, y)$, $(x, y+1)$, $(x-1, y)$, $(x, y-1)$ 중 한 위치로 이동한다. 단, 이동할 위치가 공이 있을 수 있는 위치이어야 한다.

어느 순간이든 공의 좌표 $(x, y)$는 $0\leq x\leq N$, $0\leq y\leq M$을 만족해야 한다. 이 범위 안에 있는 좌표 중에서도 공이 있을 수 없는 위치가 존재할 수 있다. 임의의 시간 $t$에 공의 $x$좌표나 $y$좌표 중 적어도 하나는 정수임에 유의하라.

그러나 이렇게만 하면 게임이 너무 쉽기 때문에, 준형이는 몇몇 스테이지에는 움직이는 장애물 $K$개를 만들었다. $i$번째 장애물은 $t=0$일 때 정수 좌표 $(x_i, y_i)$에서 시작해서 한 변의 길이가 정수 $a_i$ ($1\leq a_i\leq 5$)인 정사각형을 따라 시계방향으로 초당 1칸의 일정한 속도로 움직인다. 이때 $(x_i, y_i)$는 이 정사각형의 왼쪽 아래 꼭짓점이다. 예를 들어 $a_i=2$라면

$$(x_i, y_i)\to (x_i, y_i+1)\to(x_i, y_i+2)\to (x_i+1, y_i+2)\to (x_i+2, y_i+2)\to (x_i+2, y_i+1)\to (x_i+2, y_i)\to (x_i+1, y_i)\to (x_i, y_i)\to\cdots$$

의 경로를 따라 8초의 주기로 움직이게 된다. 움직이는 경로 위의 모든 지점은 게임판을 벗어나지 않지만, 공이 있을 수 없는 칸으로는 갈 수도 있고, 장애물끼리 경로를 공유할 수도 있다. 어떤 시간 $t$에 공과 장애물이 같은 좌표에 있게 되면 게임 오버가 된다. 여기서 $t$는 정수가 아닐 수도 있고, 공이 장애물과 만나는 지점 또한 정수 좌표가 아닐 수 있다.

준형이는 게임을 모두 만들고 나서 태영이에게 갓게임이라면서 소개해주었다. 그러나 게임은 매우 어려웠고, 태영이는 열심히 플레이해보았지만 결국 세 번째 스테이지에서 막히고 말았다. 우리가 태영이 대신 게임을 해줄 수는 없지만, 불쌍한 태영이를 위해 주어진 스테이지를 클리어하는 데 걸리는 최소 시간 정도는 구해주자.

게임을 시작할 때 멍때리고 있다가 게임오버가 되어버리거나 도착 지점으로 이동하자마자 장애물에 맞아 게임오버가 되면 너무 억울하므로, 자비로운 준형이는 이런 케이스는 만들지 않았다. 다시 말해 $K$개의 장애물의 이동경로는 시작 지점과 도착 지점을 지나지 않는다.

첫 번째 줄에 게임판의 크기 $N$과 $M$ ($1\leq N, M\leq 50$)이 주어진다. 다음 $N+1$개의 줄에는 게임판의 정보가 주어진다. $i$번째 줄 $j$번째 문자가 '.'이면 $(i-1, j-1)$에 공이 있을 수 있다는 뜻이고, '#'이면 $(i-1, j-1)$에 공이 있을 수 없다는 뜻이다. 'S'이면 시작 지점, 'E'는 도착 지점이다. 다음 줄에는 장애물의 개수 $K$ ($0\leq K\leq (N+1)(M+1) - 2$)가 주어진다. 다음 $K$개의 줄에는 장애물의 정보를 나타내는 정수 $a_i$, $x_i$, $y_i$ ($1\leq a_i\leq 5$, $0\leq x_i\leq N-a_i$, $0\leq y_i\leq M-a_i$)가 주어진다.

태영이가 게임을 클리어하는 데 걸리는 최소 시간을 출력한다. 만일 영원히 게임을 클리어할 수 없다면 INF를 출력한다.

입력 형식에 주어진 게임 판은 아래 방향이 $+x$ 방향이고, 오른쪽 방향이 $+y$ 방향이다. 또한, 장애물은 없을 ($K=0$) 수도 있다.

위 예에서는 공을 아무리 잘 움직여도 연속된 4개의 장애물이 있는 구간을 통과할 수 없다. 이 경우 게임을 클리어할 수 있는 방법이 없다. 하지만 연속된 3개의 장애물만 있다면 타이밍을 잘 맞춰서 이 구간을 통과하여 게임을 클리어할 수 있다.