숲속 미로

이 대화형 문제에서는 정체를 알 수 없는 미로의 입구에서 출구까지 시간을 너무 많이 쓰지 않고 이동해야 합니다.

유명한 전사이자 아르카니아의 영웅인 Malcolm은 어두운 숲을 밤에 걸었다. 오랫동안 걷던 그는 길을 잃은 것 같다고 생각하기 시작했지만, 길 한가운데서 갑자기 돌벽에 부딪혔다. 낙엽 아래로 보이는 돌판의 표식을 보니 드워프가 만든 미로가 분명했다.

영웅은 이 숲과 그곳의 나무에 대해 아는 것이 거의 없다. 그래도 드워프들과 오랜 시간을 함께 보낸 덕분에, 미로의 표식만 읽어도 많은 것을 알아낼 수 있다.

이 미로의 표식은 "SK3" 문자로 이루어져 있다. "S"는 미로가 정사각형이라는 뜻이다. 미로의 바닥은 한 변의 길이가 1미터인 정사각형 칸 $n \times n$개로 이루어진다. 이 칸들 둘레에는 두 개의 개구부가 있는 얇고 단단한 벽이 있다. 첫 번째는 영웅이 서 있는 입구로, 남서쪽 모서리 칸의 남쪽 벽에 있다. 두 번째는 출구로, 북동쪽 모서리 칸의 북쪽 벽에 있다.

변을 공유하는 두 칸은 통로로 연결되어 있거나, 길이 1미터의 얇은 내부 벽으로 나뉘어 있다. 각 칸에서 두 칸 사이에 벽이 없다면, 변을 공유하는 어느 칸으로든 이동할 수 있다. 출구는 자유롭게 통과할 수 있다. 입구는 영웅이 미로 안으로 들어서기 전까지만 열려 있다. 그 뒤로 닫히고, 영웅이 출구에 무사히 도착해야 다시 열린다.

"K3"는 경험 많은 미로 탐험가에게 미로의 구조를 알려준다. 먼저 가능한 내부 벽 구간 전체(남북 방향 구간이 $n \times (n - 1)$개, 동서 방향 구간도 같은 수만큼 있다) 중 3분의 1을 무작위로 고른다. 소수점 이하는 버린다. 고른 구간들은 무작위로 정한 고정된 순서에 따라 미로에 놓인다. 구간을 놓았을 때 정사각형이 분리되는 경우에는 그 구간을 버리고 놓지 않는다. 따라서 완성된 미로는 반드시 연결되어 있다.

Malcolm은 기쁘다. 미로에 대해 워낙 잘 알고 있어서 반드시 출구에 도달할 수 있기 때문이다. 그의 목표는 미로 입구 바로 옆의 숲 칸에서 출발해 미로 출구 바로 옆의 숲 칸에 도착하는 것이다. 그는 서둘러야 한다. 입구에서 출구까지 충분히 빨리 이동한 사람은 출구 근처 숲에 숨겨진 보물을 보게 된다. 다만 그 전에 아무도 보물에 도달하지 않았어야 한다.

그런데 다시 생각해 보니 걱정되는 점이 있다. 첫째, Malcolm은 미로의 크기를 모른다. 한 변의 길이 $n$은 10미터에서 200미터 사이의 어떤 정수든 될 수 있다. 둘째, 미로는 주변 숲만큼 어두워서 Malcolm은 거의 더듬으며 움직여야 한다. 매 걸음을 시작할 때 영웅은 북, 동, 남, 서 중 한 방향을 고른다. 그런 다음 그 방향으로 1미터 이동을 시도한다. 장애물에 부딪히면 제자리에 머문다. 그렇지 않으면 이웃 칸으로 이동한다. 한 걸음에 걸리는 시간은 결과와 관계없으므로, 중요한 것은 총 걸음 수다.

영웅이 필요한 칸에 충분히 빨리 도착하도록 이동을 도와라. 영웅이 최대 $5 \cdot n + 300$걸음 안에 미로 출구 바깥의 칸에 도착하면 해가 맞은 것으로 본다.