전후좌우 네 방향으로만 움직일 수 있는 드론이 있다. 이 드론은 1초 동안 1m 를 움직일 수 있고,

고도는 항상 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>은 4×4개의 타일로 구성된 미로를 나타낸다.

미로의 입구는 들어가는 화살표로 표시된 곳으로 드론이 입구 바로 밖에 대기하고 있다.

출구는 나가는 화살표로 표시된 곳이다. 미로에는 3개의 LED 타일이 있으며, 각각 1, 9, 15를 나타낸다.

수열 1, 15, 9, 15가 주어진 경우 우선 정수 1이 적힌 2행 2열 타일에 붉은색 테두리가 생기고

미로 밖 전광판에는 아직 아무것도 표시되진 않았다(<그림 2> 왼쪽).

드론을 움직여 1이 적힌 LED 타일에 도착하면 전광판에 1이 표시되고(<그림 2>가운데),

이제 수열의 다음 수인 15에 해당하는 1행 4열 타일에 붉은색 테두리가 생긴다(<그림 2> 오른쪽).

이후 드론을 움직여 15, 9, 15까지 전광판에 표시한 후 출구로 나가면 레이싱 게임

이 끝난다. 레이싱 게임 동안 드론이 움직이는 방법은 여러 가지가 있을 수 있다.

<그림 3>은 그 중 한 가지 이동 경로를 나타낸다.

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

위 예의 최솟값은 22로 <그림 3>은 그때의 이동 경로이다.

드론(drone) timer 3s memory 1024MB

드론(drone) 3s 1024MB