[15683] 감시

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

최대 8 x 8 크기의 사무실에 설치된 감시 카메라와 벽의 위치가 주어진다.

감시 카메라는 모두 5종류가 있고 최대 8 대 까지 설치 할 수 있다.

각 감시 카메라는 상 하 좌 우 방향으로 감시가 가능하다.

감시 카메라를 모두 작동시켰을 때 감시하지 못하는 최소한의 사각 지대 크기를 출력하는 문제이다.

문제에서 물어 보는 것은 최소한의 사각 지대 크기 이므로

각 감시 카메라의 방향에 따라 달라지는 사각 지대의 크기를 모두 구해야된다.

이전의 문제들 처럼 완전 탐색을 하면 된다.

백트레킹으로 각 카메라의 방향을 가지는 배열을 구해주고

방향과 감시 카메라 종류에 따라 감시 가능 지역을 칠해주고

최종적으로 남아있는 0(빈 칸)의 개수를 세주고 최소 값을 갱신하면 된다.

그렇게 어려운 문제는 아니다.

다만 노가다가 필요할 뿐.

끝.

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n, m, mini;
int arr[10][10], temp[10][10];
int visit[10];
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, 1, 0, -1};
vector<pair<int, int> > cctv;
 
void line(int x, int y, int d){
    while(1){
        x += dx[d];
        y += dy[d];
        if(x<0 || y<0 || x>=n || y>=m || temp[x][y] == 6) break;
        if(temp[x][y] == 0){
            temp[x][y] = 7;
        }
    }
}
 
void paint(int x, int y, int cc, int d){
    if(cc==1){
        line(x, y, d);
    }else if (cc==2){
        if(d==1 || d==3){
            line(x, y, 1); line(x, y, 3);
        }else if(d==2 || d==4){
            line(x, y, 2); line(x, y, 4);
        }
    }else if (cc==3){
        if(d==4){
            line(x, y, 4); line(x, y, 1);
        }else{
            line(x, y, d); line(x, y, d+1);
        }
    }else if (cc==4){
        if(d==1){
            line(x, y, 1); line(x, y, 4); line(x, y, 2);
        }else if(d==4){
            line(x, y, 4); line(x, y, 3); line(x, y, 1);
        }
        else{
            line(x, y, d); line(x, y, d-1); line(x, y, d+1);
        }
    }else if (cc==5){
        line(x, y, 1); line(x, y, 2); line(x, y, 3); line(x, y, 4);
    }
}
int scan(){
    for(int i=0; i<(int)cctv.size(); i++){
        int x = cctv[i].first;
        int y = cctv[i].second;
        paint(x, y, temp[x][y], visit[i]);
    }
    int ret = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(temp[i][j] == 0){
                ret++;
            }
        }
    }
 
    return ret;
}
 
 
void func(int num){
    if(num >= (int)cctv.size()){
        memcpy(temp, arr, sizeof(arr));
        mini = min(mini, scan());
        return ;
    }
    for(int i=1; i<=4; i++){
        visit[num] = i;
        func(num+1);
        visit[num] = 0;
    }
}
 
int main(){
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &arr[i][j]);
            if(arr[i][j] != 0 && arr[i][j] != 6){
                cctv.push_back({i, j});
            }
        }
    }
    mini = 65;
    func(0);
    printf("%d\n", mini);
    return 0;
}