라이언 킹 심바

내가 풀이한 것

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct Loc {
	int x, y, dist;
	Loc(int a, int b, int c) {
		x = a;
		y = b;
		dist = c;
	}
	bool operator<(const Loc& b)const {
		if (dist != b.dist) return dist > b.dist;
		else if (x != b.x) return x > b.x;
		return y > b.y;
	}
};
int map[26][26];
int dis[26][26];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int main() {
	int n, i, j;
	//freopen("in1.txt", "rt", stdin);
	Loc simba = Loc(0, 0, 0);
	int simba_age = 2;
	int cnt = 0, res = 0;
	priority_queue<Loc> Q;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) {
				map[i][j] = 0;
				simba = Loc(i, j, 0);
			}
		}
	}
	Q.push(Loc(simba.x, simba.y, 0));
	while (!Q.empty()) {
		Loc tmp = Q.top();
		//printf("%d %d\n", tmp.x, tmp.y);
		Q.pop();
		if (map[tmp.x][tmp.y] < simba_age && map[tmp.x][tmp.y]!=0) {
			simba = Loc(tmp.x, tmp.y, 0);
			cnt++;
			map[simba.x][simba.y] = 0;
			res += dis[tmp.x][tmp.y];
			while (!Q.empty()) Q.pop();
			for (i = 1; i <= n; i++) {
				for (j = 1; j <= n; j++) {
					dis[i][j] = 0;
				}
			}
			Q.push(Loc(simba.x, simba.y, 0));
			if (simba_age == cnt) {
				simba_age++;
				cnt = 0;
			}
		}
		for (i = 0; i < 4; i++) {
			int xx = tmp.x + dx[i];
			int yy = tmp.y + dy[i];
			if (xx<1 || xx>n || yy<1 || yy>n) continue;
			if (map[xx][yy] <= simba_age && dis[xx][yy] == 0) {
				Q.push(Loc(xx, yy, dis[tmp.x][tmp.y] + 1));
				dis[xx][yy] = dis[tmp.x][tmp.y] + 1;
			}
		}
	}
	printf("%d\n", res);
	return 0;
}