갓게임 | cho.sh

문제

태영이는 게임 중독이다. Legend of League라는 게임에 빠져 공부는 뒷전이고 하루를 게임으로 채우고 있었다. 그런 태영이를 한심하게 본 준형이는 직접 갓게임을 만들어 태영이를 Legend of League에서 꺼내기로 했다.

준형이가 만든 게임은 이렇다. 게임판은 좌표평면의 제1사분면에 있고 한 꼭짓점이 원점인 $N\times M$ 크기의 직사각형이다. $N$ 과 $M$ 은 모두 정수다. 게임의 목표는 시간 $t=0$ 에 $(startX, startY)$ 에서 출발한 공을 $(endX, endY)$ 로 옮기는 것이다. 이 좌표는 모두 정수 좌표다. 태영이는 각 정수 시간 $t$ 마다 다음 두 행동 중 하나를 한다.

공을 1초 동안 제자리에 둔다.
공의 위치가 $(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$ ) 수도 있다.

위 그림은 크기가 $1\times 7$ 인 게임판에 한 변의 길이가 1인 장애물 4개가 나란히 놓인 상황이다. 이때는 공을 아무리 잘 움직여도 장애물 4개가 이어진 구간을 통과할 수 없다. 이 경우 게임을 클리어할 수 있는 방법이 없다. 하지만 같은 자리에 장애물이 3개만 있다면 타이밍을 잘 맞춰 이 구간을 통과하여 게임을 클리어할 수 있다.