[C++] 백준 18405번 : 경쟁적전염

https://www.acmicpc.net/problem/18405

18405번: 경쟁적 전염

 

1. 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

struct cmp{
	bool operator()(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b){
		return a.first > b.first;
	}
};

int N, K, box[200][200], S, X, Y;
pair<int, int> dir[4] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, cmp> pq;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> K;

	for (int i = 0; i < N; i++){
		for (int j = 0; j < N; j++){
			cin >> box[i][j];
			if (box[i][j] != 0){
				pq.push(make_pair(box[i][j], make_pair(i, j)));
			}
		}
	}

	cin >> S >> X >> Y;
	
	for (int i = 0; i < S; i++){
		priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, cmp> cpq;


		while (!pq.empty()){
			int n = pq.top().first, cy = pq.top().second.first, cx = pq.top().second.second;
			pq.pop();

			for (int k = 0; k < 4; k++){
				int ny = cy + dir[k].first, nx = cx + dir[k].second;

				if (ny < 0 || ny >= N || nx < 0 || nx >= N || box[ny][nx] != 0)
					continue;

				box[ny][nx] = n;
				cpq.push(make_pair(n, make_pair(ny, nx)));
			}
		}

		pq = cpq;
	}

	cout << box[X-1][Y-1];

	return 0;
}