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

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

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

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

민수는 드론과 미로를 이용한 특별한 레이싱 게임을 고안했다. \(1\)부터 \(N^2\)까지의 정수로 구성된 수열 \(s_1, s_2, \ldots, s_T\)가 주어지면 전광판에 동일한 수열이 표시되도록 드론을 입구에서 출구까지 움직이면 된다. 단, 동일한 정수가 연속해 표시되는 경우는 없다고 가정한다.

항상 레이싱 게임이 끝날 수 있는 수열이 주어진다고 가정한다. 전광판에 잘못된 수열이 표시되지 않도록 \(s_1\)부터 순서대로 해당 정수가 적힌 LED 타일들의 테두리를 붉은색으로 바꾸어가고, 드론이 도착하여 전광판에 \(s_1\)이 표시되면 LED 타일들은 다시 흰색으로 바뀌며 이후 \(s_2\)가 적힌 LED 타일들의 테두리가 붉은색으로 바뀐다.

드론은 입구 바로 밖에서 대기하고 있다가 입구로 들어가고, 출구를 통과해 밖으로 나가면 레이싱 게임이 끝난다. 레이싱 게임 동안 드론이 움직이는 방법은 여러 가지가 있을 수 있다.

여러분은 레이싱 게임에 소요되는 시간의 최솟값을 계산하여 출력한다.

벽의 표현: 각 타일에 적힌 정수(\(0\)부터 \(15\)까지)는 그 타일의 네 변 중 벽이 있는 변을 다음 값의 합으로 나타낸다.

• 왼쪽 변에 벽이 있으면 \(8\)
• 아래쪽 변에 벽이 있으면 \(4\)
• 오른쪽 변에 벽이 있으면 \(2\)
• 위쪽 변에 벽이 있으면 \(1\)

두 타일 사이에 벽이 있으면 드론은 그 경계를 통과할 수 없다.

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다.

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 미로의 크기를 나타내는 정수 \(N\)이 주어진다 (\(1 \le N \le 500\)). 이어지는 \(N\)줄 각각엔 \(N\)개의 정수가 주어지는데, 각 정수는 해당 타일의 네 변에 존재하는 벽의 위치를 \(2\)진수 방식으로 표현한 것으로 \(0\)부터 \(15\)까지의 값을 가진다.

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

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

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

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2019 > 2차 대회 > 중등부 3번