백준 연구소3 C++

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

using namespace std;
const int MAX = 51;
int lab[MAX][MAX];
int copylab[MAX][MAX];
int n, m;
vector<pair<int, int>> active;
vector<pair<int, int>> virus;
int visited[MAX][MAX];
struct Move {
	int x, y;
};
Move mv[4] = { {1,0},{-1,0},{0,1},{0,-1} };
int answer = 987654321;

void checkfinish() {
	bool finish = true;
	int value = 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) {
					finish = false;
					break;
				}
				else {
					value = max(value, visited[i][j]);
				}
			}
		}
		if (finish == false)
			break;
	}
	if (finish == true) {
		answer = min(answer, value);
	}
	return;
}

void bfs() {
	queue<pair<int, int>> q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			lab[i][j] = copylab[i][j];
		}
	}

	memset(visited, -1, sizeof(visited));
	for (int i = 0; i < active.size(); i++) {
		q.push(make_pair(active[i].first, active[i].second));
		visited[active[i].first][active[i].second] = 0;
	}

	while (!q.empty()) {
		int currenti = q.front().first;
		int currentj = q.front().second;
		q.pop();

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

			if (movei >= 0 && movei < n && movej >= 0 && movej < n) {
				if (visited[movei][movej] == -1 && lab[movei][movej] != 1) {
					visited[movei][movej] = visited[currenti][currentj] + 1;
					q.push(make_pair(movei, movej));
				}
			}
		}
	}
	checkfinish();
}

void activevirus(int index, int count) {
	if (index == virus.size()) {
		if (count == m) {
			bfs();
		}
		return;
	}
	active.push_back(virus[index]);
	activevirus(index + 1, count + 1);

	active.pop_back();
	activevirus(index + 1, count);
}

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

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

	activevirus(0, 0);
	if (answer == 987654321)
		cout << -1 << endl;
	else
		cout << answer << endl;
	return 0;
}