14502 연구소

https://www.acmicpc.net/problem/14502

빈칸에 벽 3개를 세우는 모든 경우를 고려한다. 벽을 세우고 나서 BFS를 이용하여 바이러스를 확장시킨 후 남은 빈칸의 개수를 세준다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
int n,m,map[8][8],map2[8][8],ans;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
vector<pair<int,int>> e,v; // 빈칸, 바이러스 좌표
 
void bfs()
{
    queue<pair<int,int>> q;
    int size=v.size();
    for(int i=0;i<size;i++)
        q.push({v[i].first,v[i].second});
 
    while(!q.empty())
    {
        int x=q.front().first,y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(map2[nx][ny]==0)
                map2[nx][ny]=2,q.push({nx,ny});
        }
    }
}
 
void solve()
{
    int size=e.size();
    vector<int> p(size,1);
    p[0]=p[1]=p[2]=0;
 
    do
    {
        for(int i=0;i<size;i++) if(p[i]==0)
            map2[e[i].first][e[i].second]=1;
        bfs();
        int cnt=0;
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            if(map2[i][j]==0) cnt++;
        ans=max(ans,cnt);
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            map2[i][j]=map[i][j];
    } while(next_permutation(p.begin(),p.end()));
}
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&map[i][j]);
            map2[i][j]=map[i][j];
            if(map[i][j]==0)
                e.push_back({i,j});
            else if(map[i][j]==2)
                v.push_back({i,j});
        }
    }
    solve();
    printf("%d\n",ans);
    return 0;
}