BOJ 16236

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 20

struct info {
	int x;
	int y;
	int dist;
	bool operator < (const info& a) const {
		if (a.dist <= dist) {
			if (a.dist == dist) {
				if (a.x <= x) {
					if (a.x == x) {
						return a.y < y;
					}
					return true;
				}
				return false;
			}
			return true;
		}
		return false;
	}
};
struct node {
	int x;
	int y;
	int size;
	int cnt;
} shark;
priority_queue<info> pq;

bool visited[MAXN][MAXN];
int map[MAXN][MAXN];
int N;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int bfs() {
	int time = 0;
	
	while (!pq.empty()) {
		int x = pq.top().x;
		int y = pq.top().y;
		int cnt = pq.top().dist;
		if (map[x][y]!= 0 && map[x][y] < shark.size) {
			
			time += cnt;
			map[x][y] = 0;
			if (shark.size == ++shark.cnt) {
				shark.size++;
				shark.cnt = 0;
			}
			memset(visited, false, sizeof(visited));
			while (!pq.empty()) pq.pop();
			pq.push({ x,y,0 });
			visited[x][y] = true;
			continue;
		}
		pq.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N)continue;
			if (visited[nx][ny]) continue;

			if (shark.size >= map[nx][ny]) {
				visited[nx][ny] = true;
				pq.push({nx,ny,cnt+1});
			}
		}
	}
	return time;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	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) {
				map[i][j] = 0;
				shark = { i,j,2,0 };
				pq.push({ i,j, 0});
				visited[i][j] = true;
			}
		}
	}
	cout << bfs() << "\n";
	return 0;
}