연구소 3 C++

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

17142번: 연구소 3

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

const int MAX = 51;
int lab[MAX][MAX]; //0:빈칸, 1:벽, 2:바이러스 놓을 수 있는 위치
int n, m;
vector<pair<int, int>> virus;
int answer = 987654321;
int temp[MAX][MAX];
struct MOVE { int x, y; };
MOVE mv[4] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };
vector<pair<int, int>> v;
int visited[MAX][MAX];

//원래 0이엿던 얘들의 num만 계산해주기
void CheckEnd() {
	bool flag = true;
	int num = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (lab[i][j] == 0) {
				if(visited[i][j] == -1)
					return;
				else {
					if (num < visited[i][j])
						num = visited[i][j];
				}
			}
		}
	}
	if (answer > num)
		answer = num;
}

void MoveVirus() {
	memset(visited, -1, sizeof(visited));
	queue<pair<int, int>> s;
	for (int i = 0; i < v.size(); i++) {
		s.push(v[i]);
		visited[v[i].first][v[i].second] = 0;
	}

	//와일문 안끝날 수도 있음
	while (!s.empty()) {
		int ii = s.front().first;
		int jj = s.front().second;
		s.pop();

		for (int k = 0; k < 4; k++) {
			int movei = ii + mv[k].x;
			int movej = jj + mv[k].y;

			if (movei >= 0 && movei < n && movej >= 0 && movej < n && visited[movei][movej] == -1) {
				if (lab[movei][movej] != 1) {
					s.push(make_pair(movei, movej));
					visited[movei][movej] = visited[ii][jj] + 1;
				}
			}
		}
	}
	CheckEnd();
}

void SelectVirus(int index, int count) {
	if (count == m) {
		MoveVirus();
	}

	for (int i = index + 1; i < virus.size(); i++) {
		v.push_back({ virus[i].first,virus[i].second });
		SelectVirus(i, count + 1);
		v.pop_back();
	}
}

int main(void) {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lab[i][j];
			if (lab[i][j] == 2)
				virus.push_back(make_pair(i, j));
		}
	}

	SelectVirus(-1, 0);

	if (answer == 987654321)	cout << -1 << endl;
	else cout << answer << endl;
}