[BOJ 17142] 연구소 3

백준 :: BOJ :: 17142 :: 연구소 3

 

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

17142번: 연구소 3

#include <bits/stdc++.h>
using namespace std;

#define F(p,q) for(int p=0; p<q; p++)
struct S { int si, sj; };
int i, j, A[50][50], N, M, R = 1e4, c, z, r[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

int main() {
	vector<S> v; vector<int> v3;
	cin >> N >> M;
	F(i, N) F(j, N) {
		cin >> A[i][j]; if (A[i][j] > 1) { v.push_back({ i,j }); z++; } if (!A[i][j]) c++;
	}
	F(i, z - M) v3.push_back(0); F(i, M) v3.push_back(1);
	if (!c) R = 0;
	else {
		do {
			int B[50][50], dd = c, ti = 0; memcpy(B, A, sizeof(A)); queue<S> q;
			F(i, v3.size()) { if (v3[i]) { q.push(v[i]); B[v[i].si][v[i].sj] = 3; } }
			while (!q.empty()) {
				int qs = q.size(); ti++;
				while ((qs--)) {
					S ts = q.front(); q.pop();
					F(j, 4) {
						int ni = ts.si + r[j][0], nj = ts.sj + r[j][1];
						if ((ni >= 0 && nj >= 0 && ni < N && nj < N && !(B[ni][nj] % 2))) {
							q.push({ ni,nj }); if (!B[ni][nj])dd--; B[ni][nj] = 3;
						}
					}
					if (!dd) { R = min(R, ti); break; }
				}
				if (ti >= R) break;
			}
		} while (next_permutation(v3.begin(), v3.end()));
	}
	cout << (R < 1e4 ? R : -1);
	return 0;
}