#include <stdio.h>
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
typedef struct node
{
int x;
int y;
int size;
int eat;
int dist;
}node;
int map[21][21];
int N;
int ans;
queue<node> q;
int visited[21][21];
node f;
vector<node> fish;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool cmp(node A, node B)
{
// 거리가 같을 경우
if(A.dist == B.dist)
{
// 위쪽에 있는 먹이가 여러개인 경우
if(A.x == B.x)
{
// 왼쪽에 있는 먹이
if(A.y < B.y)
{
return true;
}
else
{
return false;
}
}
// 위쪽에 있는 먹이
else if(A.x < B.x)
{
return true;
}
else
{
return false;
}
}
// 가장 짧은 거리
else if(A.dist < B.dist)
{
return true;
}
else
{
return false;
}
}
int safe(int x, int y)
{
if(x >= 0 && y >= 0 && x < N && y < N)
{
return 1;
}
else
{
return 0;
}
}
void BFS()
{
while(1)
{
memset(visited, 0, sizeof(visited));
fish.clear();
visited[f.x][f.y] = 1;
q.push(f);
// 먹이가 될수있는 물고기를 찾는 반복문
while(!q.empty())
{
int x = q.front().x;
int y = q.front().y;
int size = q.front().size;
int eat = q.front().eat;
int dist = q.front().dist;
q.pop();
for(int i = 0; i < 4; i++)
{
int xpos = x+dx[i];
int ypos = y+dy[i];
// 먹이 없이 지나갈수만 있는 경우
if(safe(xpos, ypos) == 1 && (map[xpos][ypos] == 0 || map[xpos][ypos] == 9 || map[xpos][ypos] == size) && visited[xpos][ypos] == 0)
{
visited[xpos][ypos] = 1;
q.push({xpos, ypos, size, eat, dist+1});
}
// 먹이가 있는 경우
else if(safe(xpos, ypos) == 1 && map[xpos][ypos] < size && visited[xpos][ypos] == 0)
{
visited[xpos][ypos] = 1;
q.push({xpos, ypos, size, eat, dist+1});
// 먹이가 될수 있는 물고기 저장
fish.push_back({xpos, ypos, size, eat, dist+1});
}
}
}
// 먹이가 될 수 있는 물고기가 없으면 종료
if(fish.size() == 0)
{
return;
}
sort(fish.begin(), fish.end(), cmp);
// 물고기를 잡아먹음
fish[0].eat++;
// 상어의 크기 = 잡아먹은 물고기 수
if(fish[0].size == fish[0].eat)
{
fish[0].size++;
fish[0].eat = 0;
}
// 잡아 먹은 물고기 지움
map[fish[0].x][fish[0].y] = 0;
// 움직인 거리 저장
ans += fish[0].dist;
// f 초기화
f = {fish[0].x, fish[0].y, fish[0].size, fish[0].eat, 0};
}
}
int main(void)
{
// freopen("B16236_input.txt", "r", stdin);
cin >> N;
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
cin >> map[i][j];
if(map[i][j] == 9)
{
f = {i, j, 2, 0, 0};
}
}
}
BFS();
cout << ans;
return 0;
}