#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N,M,ans;
int board[10][10];
int cpy[10][10];
bool vis[10][10];
vector<pair<int,int>> virus;
vector<pair<int,int>> zero;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
{
cin >> board[i][j];
if(board[i][j] == 2)
virus.push_back({i,j});
else if(board[i][j] == 0)
zero.push_back({i,j});
}
}
int ch[zero.size()];
fill(ch, ch+zero.size(), 1);
for(int i=0;i<3;i++) ch[i] = 0;
do{
queue<pair<int,int>> q;
for(int i=0;i<N;i++)
{
fill(vis[i], vis[i]+M, false);
for(int j=0;j<M;j++)
cpy[i][j] = board[i][j];
}
for(int i=0;i<zero.size();i++)
if(ch[i] == 0)
cpy[zero[i].first][zero[i].second] = 1;
for(int i=0;i<virus.size();i++)
{
vis[virus[i].first][virus[i].second] = true;
q.push(virus[i]);
}
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(nx<0 or ny<0 or nx>=M or ny>=N) continue;
if(vis[ny][nx] or cpy[ny][nx] == 1) continue;
q.push({ny,nx});
vis[ny][nx] = true;
cpy[ny][nx] = 2;
}
}
int cnt=0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(cpy[i][j] == 0) cnt++;
ans = max(ans, cnt);
}while(next_permutation(ch, ch+zero.size()));
cout << ans;
return 0;
}
- 로직
next_permutation()
으로 모든 '0' 좌표
중 3개를 선택
해서 '1'로 바꾸고
BFS
를 실행
'0'
카운드
하여 최대값 카운트
next_permutation()
이 없으면?
: 3-depth인 재귀
를 통해 3개의 '0'좌표
를 '1'
로 바꾼 뒤 BFS
수행!