15683 감시

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

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n,m,cnt,ans=100,map[8][8],tmap[8][8];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; // 북동남서
vector<pair<pair<int,int>,pair<int,int>>> v;
int size,p[8];
 
void go(int x,int y,int d)
{
 
    while(true)
    {
        int nx=x+dx[d],ny=y+dy[d];
        if(nx<0 || nx>=n || ny<0 || ny>=m || tmap[nx][ny]==6)
            break;
        tmap[nx][ny]=-1;
        x=nx,y=ny;
    }
}
 
void solve()
{
    cnt=0;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        tmap[i][j]=map[i][j];
    for(int i=0;i<size;i++)
    {
        int t=v[i].first.first;
        int d=p[i];
        int x=v[i].second.first;
        int y=v[i].second.second;
        if(t==1) go(x,y,d);
        else if(t==2) go(x,y,d),go(x,y,d+2);
        else if(t==3) go(x,y,d),go(x,y,d==3?0:d+1);
        else if(t==4)
        {
            if(d==0) go(x,y,3),go(x,y,0),go(x,y,1);
            else if(d==3) go(x,y,2),go(x,y,3),go(x,y,0);
            else go(x,y,d-1),go(x,y,d),go(x,y,d+1);
        }
        else
        {
            for(int j=0;j<4;j++)
                go(x,y,j);
        }
    }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        if(!tmap[i][j]) cnt++;
    ans=min(ans,cnt);
}
 
void make(int idx)
{
    if(idx==size)
    {
        solve();
        return;
    }
    int range=v[idx].first.second;
    for(int i=0;i<range;i++)
        p[idx]=i,make(idx+1);
}
 
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]);
            int t=map[i][j];
            if(t>=1 && t<=5)
            {
                v.push_back({{t,t==2?2:4},{i,j}});
                size++;
            }
        }
    }
    make(0);
    printf("%d\n",ans);
    return 0;
}