C++
#include <cstdio>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;
int N,M,num0;
int area=0;
vector <pair<int,int>> virus;
int map_[10][10];
int map2 [10][10];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void spread(int x,int y){
for(int i=0;i<4;i++){
int ax=x+dx[i],ay=y+dy[i];
if(ax<0||ay<0||ax>=M||ay>= N){
continue;
}
if(map2[ay][ax]==0){
area++;
map2[ay][ax]=2;
spread(ax,ay);
}
}
}
int main()
{
scanf("%d %d",&N,&M);
for(int y=0;y<N;y++){
for(int x=0;x<M;x++){
scanf("%d",&map_[y][x]);
if(map_[y][x]==2){
virus.push_back({x,y});
}
if(map_[y][x]==0){
num0++;
}
}
}
int min_virus_area = INT_MAX;
int size_ = N * M;
for(int i = 0; i < size_; ++i)
{
if(map_[i / M][i % M])
continue;
for(int j = i + 1; j < size_; ++j)
{
if(map_[j / M][j % M])
continue;
for(int k = j + 1; k < size_; ++k)
{
if(map_[k / M][k % M])
continue;
memcpy(map2, map_, sizeof(map_));
map2[i / M][i % M] = 1;
map2[j / M][j % M] = 1;
map2[k / M][k % M] = 1;
int virus_area = 0;
for(auto &v: virus)
{
area=0;
spread(v.first, v.second);
virus_area += area;
}
min_virus_area = min(min_virus_area, virus_area);
}
}
}
printf("%d",num0-min_virus_area-3);
return 0;
}
댓글 0
번호 | 제목 | 글쓴이 | 날짜 | 조회 수 |
---|---|---|---|---|
공지 | 안내사항 | 관리자 | 2019.12.21 | 164 |
74 | 9663 | 관리자 | 2019.12.21 | 115 |
73 | 9345 | 관리자 | 2020.04.11 | 151 |
72 | 9019 | 관리자 | 2019.12.21 | 114 |
71 | 7569 | 관리자 | 2019.12.21 | 114 |
70 | 6987 | 관리자 | 2019.12.21 | 114 |
69 | 5842 | 관리자 | 2020.04.11 | 152 |
68 | 5625 | 관리자 | 2019.12.21 | 110 |
67 | 5419 | 관리자 | 2020.04.11 | 157 |
66 | 3392 | 관리자 | 2020.04.11 | 157 |
65 | 3019 | 관리자 | 2019.12.21 | 112 |
64 | 2933 | 관리자 | 2019.12.21 | 113 |
63 | 2931 | 관리자 | 2019.12.21 | 112 |
62 | 2836 | 관리자 | 2019.12.21 | 111 |
61 | 2667 | 관리자 | 2019.12.21 | 114 |
60 | 2636 | 관리자 | 2019.12.21 | 114 |
59 | 2629 | 관리자 | 2020.04.11 | 147 |
58 | 2615 | 관리자 | 2019.12.21 | 112 |
57 | 2610 | 관리자 | 2020.04.11 | 147 |
56 | 2606 | 관리자 | 2019.12.21 | 112 |
55 | 2585 | 관리자 | 2019.12.21 | 114 |
54 | 2578 | 관리자 | 2019.12.21 | 112 |
53 | 2573 | 관리자 | 2020.04.11 | 152 |
52 | 2557 | 관리자 | 2019.12.21 | 112 |
51 | 2512 | 관리자 | 2019.12.21 | 112 |
50 | 2504 | 관리자 | 2020.04.11 | 148 |
49 | 2481 | 관리자 | 2019.12.21 | 113 |
48 | 2478 | 관리자 | 2020.04.11 | 149 |
47 | 2473 | 관리자 | 2020.04.11 | 154 |
46 | 2470 | 관리자 | 2020.04.11 | 152 |