16236번 아기 상어

내가 처음 올린 심바와 똑같은 문제이다. 다시 푸니까 감회가 새롭당
아기 상어가 <먹이를 먹을 수 있는지>, <먹이를 찾으러 출발>부분으로 나누어서 풀었다. 코드에서 simba가 아기 상어다.

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
//memset(ch,0,sizeof(ch));
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int n;
struct Loc{
	int x, y, dis;
	Loc(int a, int b, int c) {
		x = a;
		y = b;
		dis = c;
	}
	bool operator< (const Loc& b) const {
		if (dis != b.dis) return dis > b.dis;
		if (x != b.x) return x > b.x;
		return y > b.y;
	}
};
struct sim {
	int x, y;
	sim(int a, int b) {
		x = a;
		y = b;
	}
};

int map[21][21];
int ch[21][21];
void f() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << map[i][j] << " ";
		}
		cout << '\n';
	}
}
int main() {
	//freopen("in1.txt", "rt", stdin);
	int m;
	int sum = 0;
	int simba_age = 2;
	sim simba = sim(0, 0);
	int cnt = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 9) {
				simba.x = i;
				simba.y = j;
				map[i][j] = 0;
			}
		}
	}
	
	priority_queue<Loc> Q;
	Q.push(Loc(simba.x, simba.y, 0));
	while (!Q.empty()) {
		Loc tmp = Q.top();
		Q.pop();
		if (map[tmp.x][tmp.y]!=0&&map[tmp.x][tmp.y]<simba_age) {
			cnt++;
			sum+=tmp.dis;
			map[tmp.x][tmp.y] = 0;
			if (cnt == simba_age) {
				simba_age++;
				cnt = 0;
			}
			tmp.dis = 0;
			while (!Q.empty()) Q.pop();
			memset(ch, 0, sizeof(ch));
		}
		for (int i = 0; i < 4; i++) {
			int xx = tmp.x + dx[i];
			int yy = tmp.y + dy[i];
			if (xx > n || xx<1 || yy>n || yy < 1)continue;
			if (ch[xx][yy]==0&&map[xx][yy] <= simba_age) {
				ch[xx][yy] = 1;
				Q.push(Loc(xx, yy, tmp.dis + 1));
			}
		}
	}
	cout << sum << '\n';
	return 0;
}