25969번 - 현대 모비스 자율 주행 시스템

현대 모비스의 서산 주행 시험장에서 현대 모비스의 새로운 자율 주행 시스템이 적용된 부품을 사용한 모빌리티가 주행 시험을 하고 있다. 이 시스템은 인공위성에서 모빌리티 주위를 인식해 현재 위치에서 목적지로 가기 위한 최단 거리를 계산한다. 기존의 시스템은 모빌리티의 상하좌우 만으로 이동하며 최단 거리를 계산했지만, 새로운 시스템은 상하좌우로 이동할 수 있을 뿐만 아니라 이동할 수 있는 추가 패턴으로 이동하며 최단 거리를 계산한다. 하지만 인공위성과 계속 통신하지는 못하기 때문에, 이 추가 패턴들을 무한정 사용하지는 못한다.

승준이는 이 자율 주행 시스템을 통하여 왼쪽 최상단으로 고정된 출발지에서, 중간 거점지들 중에 최소 하나를 거쳐서 오른쪽 최하단으로 고정된 최종 목적지까지 가는 최단거리를 구하는 것을 시험하고 있다. 목적지가 중간 거점에 포함될 수 있으며, 이 경우에는 중간 거점을 방문한 후 목적지에 도착한 것으로 간주한다. 인공위성에서 모빌리티 주위를 인식한 지도, 이동할 수 있는 추가 패턴 그리고 패턴의 사용 횟수가 주어질 때 출발점에서 시작하여 중간 거점지들 중 최소 하나를 거쳐 최종 목적지로 가는 최단 거리를 구하는 프로그램을 작성하시오.

패턴은 $5 \times 5$ 크기의 배열 형태로 주어진다. 배열의 $3$행 $3$열에는 모빌리티가 위치해 있다. $A$행 $B$열이 $1$이라면, 시스템이 모빌리티가 $3$행 $3$열 기준으로 $A$행 $B$열로 이동할 수 있는 형식의 패턴을 사용할 수 있다는 의미이다.

첫째 줄에 세로 크기 $N$ 과 가로 크기 $M$ 패턴의 사용 횟수 $K$가 주어진다. $(1 \leq N,M \leq 200, 0 \leq K \leq 30)$

지도는 세로가 $N$, 가로가 $M$인 크기의 지도 모양으로 주어진다. 0이 빈칸, 1이 벽, 2가 중간 거점지를 뜻하며, 모빌리티는 벽인 곳으로는 이동할 수 없다. 또한 모빌리티는 지도 밖으로 이동할 수 없다. 지도의 왼쪽 최상단(시작 지점)은 0임이 보장된다.

그 다음 5줄에 거쳐 $5 \times 5$ 크기의 패턴 배열이 주어진다. 패턴 배열은 0 또는 1로 주어진다.

출발지에서 출발하여 중간 거점지들 중 최소 하나를 거쳐 목적지로 가는 최단 거리를 출력한다. 어떤 경우에도 중간 거점지들 중 최소 하나를 거쳐 목적지로 이동할 수 없는 경우에는 -1를 출력한다.