17142研究所3

コードの説明

コード#コード#

#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int N, M;
int map[51][51];
vector<pair<int, int> > wall;
vector<pair<int, int> > virus;
vector<pair<int, int>> real_virus;
int time_map[51][51];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
int empty_place;
int answer=9999;
bool flag;

void BFS() {
	//큐에 인덱스 등록
	int total_time = 0;
	int infect_room = 0;
	int cnt = 0;
	queue<pair<int, int>> q;
	for (int i = 0; i < real_virus.size(); i++) {
		q.push({ real_virus[i].first,real_virus[i].second });
		
	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] == 1) { //벽일경우
				time_map[y][x] = -2;
			}
		}
	}

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
			// 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.(1초소요)
			if (time_map[ny][nx] == -1) {
				q.push({ ny,nx });
				time_map[ny][nx] = time_map[y][x] + 1;
				if (map[ny][nx]==0) {
					infect_room++;
					total_time = time_map[ny][nx];
				}
			}
		}
	}



	if(infect_room == empty_place) answer = min(answer, total_time);

	
}

void run(int level,int now) {
	if (level == M) {//바이러스 위치 M개 정하기
		for (int i = 0; i < real_virus.size(); i++) {
			time_map[real_virus[i].first][real_virus[i].second] = 0;
		}
		
		BFS();
		

		memset(time_map, -1, sizeof(time_map));
		return;
	}
	for (int i = now; i < virus.size(); i++) {
		real_virus.push_back({ virus[i].first,virus[i].second });

		run(level + 1, i + 1);
		real_virus.pop_back();
	}


}
int main() {

	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
			if (map[y][x] == 0) {
				empty_place++;
			}
			if (map[y][x] == 1) {
				wall.push_back({ y,x });
				
			}
			if (map[y][x] == 2) {
				virus.push_back({ y,x });
			}

		}
	}
	memset(time_map, -1, sizeof(time_map));
	run(0, 0); //바이러스 M개 고르기
	if (answer==9999) cout << -1;
	else cout << answer;



	return 0;
}