17620번 - 드론 서브태스크채점 준비 중

전후좌우 네 방향으로만 움직일 수 있는 드론이 있다. 이 드론은 1초 동안 m를 움직일 수 있고, 고도는 항상 1m를 유지한다. 드론의 크기는 1m²의 정사각형에 겨우 들어갈 정도이다.

드론에는 정수 인식 센서가 달려있어서, 드론의 아래에 정수가 위치하면 이를 외부 전광판에 표시한다. 다만 이 센서는 붉은색 테두리 안에 있는 정수만 인식할 수 있다.

민수는 드론이 이동할 수 있는 미로를 만들었다. 미로의 바닥은 1m² 크기의 정사각형 타일이 N×N 격자로 배치된 정사각형 형태이다. 이 미로는 입구와 출구만 제외하곤 높이 2m인 벽으로 둘러 쌓여있다. 입구는 항상 1행 1열의 왼쪽 부분이고, 출구는 항상 N행 N열의 오른쪽 부분이다. 그리고 미로 내부에는 한 변이 맞닿은 두 타일 사이에 폭 1m, 높이 2m인 벽이 있을 수 있다.

미로의 타일은 모두 흰색이지만, 일부 타일은 LED로 만들어져서 필요한 경우 타일 테두리를 붉은색으로 바꿀 수 있다. 물론 다시 흰색으로도 바꿀 수 있다. 그리고 LED 타일에는 1부터 N²까지 정수 중 하나의 수가 적혀있다. 미로에는 같은 수가 적힌 LED 타일이 여러 개 있을 수도 있다.

민수는 드론과 미로를 이용한 특별한 레이싱 게임을 고안했다. 1부터 N²까지의 정수로 구성된 수열 s₁, s₂, ..., s_T가 주어지면 전광판에 동일한 수열이 표시되도록 드론을 입구에서 출구까지 움직이면 된다. 단, 동일한 정수가 연속된 경우는 없다고 가정한다. 또한 항상 레이싱 게임이 끝날 수 있는 수열이 주어진다고 가정한다. 전광판에 잘못된 수열이 표시되지 않도록 s₁부터 순서대로 해당 정수가 적힌 LED 타일들의 테두리를 붉은색으로 바꾸고, 드론이 도착하여 전광판에 s₁이 표시되면 LED 타일들은 다시 흰색으로 바뀌며 이제 s₂가 적힌 LED 타일들의 테두리가 붉은색으로 바뀐다.

<그림 1>

예를 들어, <그림 1>은 4×4개의 타일로 구성된 미로를 나타낸다. 미로의 입구는 들어가는 화살표로 표시된 곳으로 드론이 입구 바로 밖에 대기하고 있다. 출구는 나가는 화살표로 표시된 곳이다. 미로에는 3개의 LED 타일이 있으며, 각각 1, 9, 15를 나타낸다.

<그림 2>

수열 1, 15, 9, 15가 주어진 경우 우선 정수 1이 적힌 2행 2열 타일에 붉은색 테두리가 생기고 미로 밖 전광판에는 아직 아무것도 표시되진 않았다(<그림 2> 왼쪽). 드론을 움직여 1이 적힌 LED 타일에 도착하면 전광판에 1이 표시되고(<그림 2> 가운데), 이제 수열의 다음 수인 15에 해당하는 1행 4열 타일에 붉은색 테두리가 생긴다(<그림 2> 오른쪽)

<그림 3>

이후 드론을 움직여 15, 9, 15까지 전광판에 표시한 후 출구로 나가면 레이싱 게임이 끝난다. 레이싱 게임 동안 드론이 움직이는 방법은 여러 가지가 있을 수 있다. <그림 3>은 그 중 한 가지 이동 경로를 나타낸다.

여러분은 레이싱 게임에 소요되는 시간의 최솟값을 계산하여 출력한다. 위 예의 최솟값은 22로 <그림 3>은 그때의 이동 경로이다.

첫 번째 줄에 미로의 크기를 나타내는 정수 N이 주어진다(1 ≤ N ≤ 500). 이어지는 N줄 각각엔 N개의 정수가 주어지는데 각 정수는 해당 타일의 네 변에 존재하는 벽의 위치를 <그림 4>에서 보인 것처럼 2진수 방식으로 표현한 것으로 0부터 15까지의 값을 가진다.

<그림 4>

다음 줄에는 LED 타일의 개수를 나타내는 정수 M(1 ≤ M ≤ min{N², 100})이 주어지고, 이어지는 M개 줄 각각에 LED 타일의 위치 x_i행 y_i열(1 ≤ i ≤ M)과 타일에 적힌 정수 c_i가 차례대로 주어진다(1 ≤ x_i, y_i ≤ N, 1 ≤ c_i ≤ N²).

다음 줄에는 수열의 크기를 나타내는 정수 T(1 ≤ T ≤ 1000)가 주어지고, 이어지는 줄에 T개의 정수 s_j(1 ≤ j ≤ T)가 주어진다(1 ≤ s_j ≤ N²). 이때 모든 s_j에 대해 s_j = c_i이면서 해당 LED 타일 위치에 드론이 도달할 수 있는 c_i가 존재한다. 또한 모든 s_k(1 ≤ k < T)에 대해 s_k ≠ s_k+1이다.

레이싱 게임에 소요되는 시간의 최솟값을 정수로 출력한다.