게임의 이동 횟수

2048은 정사각형 격자에서 숫자 타일을 밀어 같은 값끼리 합치고, 점점 더 큰 값을 만드는 퍼즐 게임이다. 원래 목표는 2048 타일을 만드는 것이지만, 2048 타일을 만들었는지와 상관없이 더 이상 이동할 수 없을 때까지 게임이 이어진다. 게임은 빈 보드의 무작위 위치에 값이 2 또는 4인 타일 두 개가 놓인 상태에서 시작한다.

게임은 이동을 반복하며 진행되고, 이동 한 번은 다음 다섯 단계로 이루어진다. 방향 선택, 밀기, 합치기, 빈틈 메우기, 생성이다.

1. 방향 선택: 플레이어가 위, 아래, 왼쪽, 오른쪽 중 하나를 고른다. 고른 방향을 하류라고 한다.
2. 밀기: 모든 타일을 하류로 갈 수 있는 만큼 밀어 빈틈을 없앤다. 타일이 밀려가 닿는 보드의 변을 막는 변이라고 한다.
3. 합치기: 막는 변에서 멀어지는 상류 방향으로 살펴보면서, 상류 쪽 이웃과 값이 같은 타일은 그 이웃과 합쳐져 두 값의 합을 값으로 갖는 타일 하나가 된다. 합쳐서 나온 타일은 같은 이동에서 다시 합쳐지지 않는다. 두 타일이 합쳐질 때마다 점수가 새로 생긴 타일의 값만큼 올라간다.
4. 빈틈 메우기: 모든 타일을 다시 하류로 갈 수 있는 만큼 밀어 빈틈을 없앤다.
5. 생성: 빈 칸 하나에 값이 2 또는 4인 타일이 새로 나타난다. 값과 위치는 모두 무작위이다.

둘째 단계나 셋째 단계에서 보드가 어떤 식으로든 바뀌어야 유효한 이동이고, 이때만 새 타일이 나타난다.

점수는 0에서 시작하고, 두 타일이 합쳐질 때마다 새로 생긴 타일의 값만큼 올라간다. 보통 $4 \times 4$ 격자에서 하지만 크기가 다른 정사각 격자로도 한다.

(a) 점수는 16

(b) 아래로 이동, 점수는 24

(c) 아래로 이동, 점수는 32

(d) 아래로 이동, 점수는 48

그림 1: 여러 번 이동하는 동안의 점수 변화. 새로 나타난 값은 파란색으로 표시했다.

그림 1은 점수가 16에서 24, 32, 48로 올라가는 과정을 보여준다. 출발점인 그림 1(a)는 일곱 번 이동한 뒤의 상태이다. 플레이어가 아래로 이동하면 셋째 열과 넷째 열에 있는 세로 방향 2 두 쌍이 각각 4가 된다. 4가 두 개 생기므로 점수가 8 올라간다. 그 결과가 그림 1(b)이고, 둘째 열에 2가 무작위로 새로 나타났다. 플레이어가 아래로 다시 이동하면 넷째 열의 세로 방향 4 한 쌍이 8이 되고, 점수가 합쳐진 값의 합만큼, 즉 8 올라간다. 보드는 그림 1(c)가 되고 넷째 열에 4가 무작위로 나타났다. 마지막으로 아래로 한 번 더 이동하면 넷째 열의 세로 방향 8 한 쌍이 16이 되어 점수가 16 올라간다. 그 결과가 그림 1(d)이다.

(a) 현재 상태

(b) 오른쪽으로 이동한 뒤

(c) 왼쪽으로 이동한 뒤

그림 2: 값이 합쳐지고 움직이는 방식

그림 2는 값이 합쳐지고 움직이는 방식을 보여주는 설명용 그림이며, 새 타일이 나타나는 모습은 담지 않았다. 보드가 그림 2(a) 상태일 때 플레이어가 오른쪽으로 이동하면 아래 행의 가로 방향 2 두 쌍이 각각 4가 되지만(그림 2(b)), 위 행에서는 오른쪽에 있는 4 한 쌍만 8이 된다. 이어서 왼쪽으로 이동하면 아래 행의 가로 방향 4 한 쌍이 8 하나가 되고(그림 2(c)), 위 행의 값은 움직이기만 하고 합쳐지지 않는다.

게임의 상태와 현재 점수가 주어질 때, 그 상태에 이르기까지 이동한 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 정사각 격자의 크기 $n$이 주어진다 ($2 \le n \le 7$).

다음 $n$개의 줄에는 각각 $n$개의 정수가 공백으로 구분되어 주어지고, 게임의 현재 상태를 나타낸다. 값이 0인 칸은 빈 칸이다. 빈 칸이 아닌 칸의 값은 2 이상 $2^{50}$ 이하인 2의 거듭제곱이다.

마지막 줄에 현재 상태의 점수 $s$가 주어진다 ($0 \le s \le 108086391056891712$).

입력으로 주어지는 상태는 항상 실제 게임에서 나올 수 있는 상태이다.

현재 상태에 이르기까지 이동한 횟수를 출력한다. 답은 $2^{63}$보다 작다.