백준 - 아기 상어 [16236]

#include<iostream>
#include <algorithm>
#include <queue>
#include <vector>


using namespace std;

int m_size = 0;

int map[20][20];
bool v[20][20];
int result = 0;
int time = 0;

bool flag = false;
bool flag2 = false;
pair<int, pair<int, int>> s_info;

priority_queue<int, vector<int>, greater<int> > pq;
queue<pair<int, pair<int, int>>> q;
queue<pair<int, pair<int, int>>> w;
vector<pair<int, int>> list;
int cur = 0;

void checking(int i, int j, int info) {
	v[i][j] = true;
	if (map[i][j] == 0 || map[i][j] == s_info.first) {
		q.push(make_pair(map[i][j], make_pair(i, j)));
		flag2 = true;
	}
	else if (map[i][j] > s_info.first) {
		return;
	}
	else {
		flag = true;
		flag2 = true;
		list.push_back(make_pair(i, j));

	}

}


int bfs(int info) {

	pair<int, pair<int, int>> temp;
	int i;
	int j;
	int size;
	int left;
	int up;
	v[s_info.second.first][s_info.second.second] = true;
	while (!q.empty()) {

		w = q;
		time++;
		while (!q.empty())
			q.pop();

		while (!w.empty()) {
			temp = w.front();

			i = temp.second.first;
			j = temp.second.second;
			size = s_info.first;


			if (i > 0 && !v[i - 1][j]) checking(i - 1, j, info);
			if (j > 0 && !v[i][j - 1]) checking(i, j - 1, info);
			if (j < m_size - 1 && !v[i][j + 1]) checking(i, j + 1, info);
			if (i < m_size - 1 && !v[i + 1][j])checking(i + 1, j, info);

			w.pop();
		}
		if (flag)
			break;

	}
	if (flag) {
		sort(list.begin(), list.end());
		up = list[0].first;
		left = list[0].second;
		map[up][left] = 0;
		cur++;
		s_info.second.first = up;
		s_info.second.second = left;
		if (cur == s_info.first) {
			s_info.first++;
			cur = 0;
		}

		for (int i = 0; i < m_size; i++) {
			for (int j = 0; j < m_size; j++) {
				v[i][j] = false;
			}
		}
	}
	else {
		time = 0;
	}
	list.clear();
	while (!q.empty())
		q.pop();
	while (!w.empty())
		w.pop();
	return time;
}

int main() {
	int bs = 2;
	pair<int, pair<int, int>> info;

	cin >> m_size;

	for (int i = 0; i < m_size; i++) {
		for (int j = 0; j < m_size; j++) {
			cin >> map[i][j];
			info.first = map[i][j];
			info.second.first = i;
			info.second.second = j;
			if (map[i][j] == 9) {
				s_info = info;
				s_info.first = 2;
				map[i][j] = 0;
			}
			else if (info.first != 0) {
				pq.push(info.first);
			}

		}
	}

	while (!pq.empty()) {
		q.push(make_pair(s_info.first, make_pair(s_info.second.first, s_info.second.second)));
		bfs(pq.top());
		if (!flag2)
			break;
		result += time;
		time = 0;
		pq.pop();
		if (!pq.empty() && pq.top() >= s_info.first)
			break;
		flag = false;
		flag2 = false;
	}
	cout << result;

	return 0;
}