17142. 연구소3

고려사항

1. 비활성화 세포가 활성화될 수 있다는 것을 인지하자 => 마지막에 비활성화세포가 활성세포가 되도, 큐에 넣지 않거나 시간 카운팅을 하면 안 되다.

2. 벽에 막혀서 세포번식이 안되는 경우를 생각하자.  

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef struct m {
	int i;
	int j;
};
typedef struct q {
	int i;
	int j;
	int t;
};

int maxs = 100000;
int N, M;
int map[55][55]; 
int emptys = 0;

int dx[] = { 0,1,0,-1 };
int dy[] = { -1,0,1,0 };

int simul(vector<m> list) {
	int make_map[55][55] = { 0 };
	queue<q> qu;
	if (emptys == 0)
		return 0;
	for(int i=0;i<N;i++){
		for (int j = 0; j < N; j++) {
			make_map[i][j] = map[i][j];
		}
	}
	for (int i = 0; i < list.size(); i++) {
		qu.push({ list[i].i ,list[i].j,0});
		make_map[list[i].i][list[i].j] = 5;
	}
	qu.push({ -1,-1,-1 });
	int answer = 0;
	int count = 0;
	while (!qu.empty()) {
		int i = qu.front().i;
		int j = qu.front().j;
		int t = qu.front().t;
		qu.pop();
		if (i == -1) {
			if (qu.empty())
				break;
			answer++;
			if (count == emptys)
				break;
			i = qu.front().i;
			j = qu.front().j;
			t = qu.front().t;
			qu.pop();
			qu.push({ -1,-1,-1 });
		}

		if (t > maxs)
			return -1;
		for (int k = 0; k < 4; k++) {
			if (i + dx[k] < N && i + dx[k] >= 0 && j + dy[k] >= 0 && j + dy[k] < N) {
				if (make_map[i + dx[k]][j + dy[k]] == 0) {
					count++;
					make_map[i + dx[k]][j + dy[k]] = t + +5;
					qu.push({i + dx[k], j + dy[k], t + 1});
				}
				if (make_map[i + dx[k]][j + dy[k]] == 2) {
					make_map[i + dx[k]][j + dy[k]] = t + 5;
					qu.push({ i + dx[k], j + dy[k], t });
				}
			}
		}
	}
	if (count != emptys)
		answer = -1;
	return answer;
}

void pick_point(vector<m> list, vector<m> v_list , int point) {

	if (list.size() == M) {
		int box=simul(list);
		if (box == -1)
			return;
		if (maxs > box)
			maxs = box;
		return;
	}
	if (point >= v_list.size()) {
		return;
	}
	pick_point(list, v_list, point + 1);
	list.push_back(v_list[point]);
	pick_point(list, v_list, point + 1);
}

int main() {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	cin >> N >> M;
	
	vector<m> list;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				list.push_back({ i,j });
			}
			if (map[i][j] == 0) {
				emptys++;
			}
		}
	}
	vector<m> li;
	pick_point(li, list, 0);
	if (maxs == 100000)
		maxs = -1;

	cout << maxs;

	return 0;
}

 

 

www.acmicpc.net/problem/17142

17142번: 연구소 3