백준
백준 소스코드 [C++] 14502 연구소
Hani_Levenshtein
2020. 8. 24. 13:07
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크�
www.acmicpc.net
백준 소스코드 [C++] 14502 연구소
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
pair<int, int> pp,p[4] = { {1,0},{-1,0},{0,1},{0,-1} };
int arr[10][10];
bool check[10][10];
int n, m,sum,pollution,maxpollution=987654321;
queue <pair<int, int>>q;
void bfs() {
while (q.empty() != true) {
pp = q.front();
q.pop();
for(int i=0;i<4;i++)
if (arr[pp.first + p[i].first][pp.second + p[i].second] == 0 &&
check[pp.first + p[i].first][pp.second + p[i].second] == true) {
arr[pp.first + p[i].first][pp.second + p[i].second] =3;
q.push(make_pair(pp.first + p[i].first, pp.second + p[i].second));
pollution++;
}
}
}
void dfs(int y,int x,int w) {
if (w == 3) {
pollution = 0;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
if (arr[i][j] == 2) {
q.push(make_pair(i, j));
bfs();
}
maxpollution = min(maxpollution, pollution);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
if (arr[i][j] == 3) arr[i][j] = 0;
return;
}
else {
for (int i = y;i <= n;i++)
for (int j = x;j <= m;j++) {
if (j == m)x = 0;
if (check[i][j] == true && arr[i][j] == 0) {
check[i][j] = false;
dfs(i, j, w + 1);
check[i][j] = true;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
sum = n * m;
for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) {
cin >> arr[i][j];
if (arr[i][j] == 0) check[i][j] = true;
else sum--;
}
dfs(1,1,0);
cout << sum-maxpollution-3;
return 0;
}