만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

현대 모비스 자율 주행 시스템

면접 대비

시간 제한1초메모리 제한512 MB

요약
왼쪽 위에서 오른쪽 아래까지 경유지를 최소 하나 거치는 최단 거리를 구하며, 5x5 패턴 이동은 최대 K번까지 쓸 수 있습니다.
난이도

보통10점 중 5점

유형
BFS, 최단 경로, 그래프
정답자
아직 제출이 없습니다

문제

현대 모비스의 서산 주행 시험장에서 새로운 자율 주행 시스템을 적용한 부품을 단 모빌리티가 주행 시험을 하고 있다. 이 시스템은 인공위성으로 모빌리티 주변을 인식해서 현재 위치에서 목적지까지의 최단 거리를 계산한다. 기존 시스템은 모빌리티를 상하좌우로만 움직여 최단 거리를 계산했다. 새로운 시스템은 상하좌우 이동에 더해 추가 패턴으로도 이동하며 최단 거리를 계산한다. 다만 인공위성과 계속 통신할 수 없으므로, 추가 패턴은 무한정 사용할 수 없다.

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

패턴은 5×55 \times 5 크기의 배열로 주어진다. 배열의 33행 33열에는 모빌리티가 있다. AA행 BB열의 값이 11이면, 모빌리티를 33행 33열 기준으로 AA행 BB열 위치로 이동시키는 패턴을 사용할 수 있다는 뜻이다.

입력

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

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

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

출력

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

예제3

  1. 예제 1

    입력
    3 3 0
0 1 2
0 1 0
0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
    예상 출력
    8

  2. 예제 2

    입력
    9 7 4
0 2 0 0 0 1 2
2 0 0 2 0 2 2
2 1 1 1 2 0 0
0 1 1 1 0 0 1
2 0 0 2 1 0 1
1 2 2 2 1 1 2
1 2 1 1 2 1 0
2 1 2 2 0 1 1
2 1 2 0 1 2 2
1 0 1 0 0
0 0 0 1 0
1 0 1 1 0
0 0 1 1 1
0 0 1 0 0
    예상 출력
    7

  3. 예제 3

    입력
    4 10 2
0 0 0 1 1 2 1 2 1 2
2 1 2 0 2 2 0 0 1 0
1 0 1 2 2 2 2 1 2 2
2 2 1 0 1 1 0 1 0 1
1 0 0 0 1
1 1 0 0 1
1 0 0 0 1
1 0 1 0 0
0 0 1 1 1
    예상 출력
    -1