감시_15683

문제 출처 : 감시_15683 문제

파라미터 정리

NxM 셀, N: row, M: col
K 개의 카메라 有 (최대 8개)
0: 빈 칸
1~5: 카메라
-1번 카메라 : {1 0 0 0} 총 4방법
-2번 카메라 : {1 0 1 0} 총 2방법
-3번 카메라 : {1 1 0 0} 총 4방법
-4번 카메라 : {1 1 1 0} 총 4방법
-5번 카메라 : {1 1 1 1} 총 1방법
6: 벽
9: 감시된 곳

간략한 과정

input_1 N,M 입력받기 (1 ~ 8)
input_2 Map[8][8] 변수에 초기 정보 입력 받기
이때 카메라 입력받으면 카메라 정보도 저장하기
각 카메라 별로 발생하는 감시 방법 조사하기
벽(6)을 만날 때까지/끝에 닿을 때까지 감시받는 영역 그리기
모든 카메라 사용한 후 빈 칸 수 세기
각 감시 방법에 대해 최소값 비교하기
output 사각 지대의 최소값 출력하기

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define INF 9845657

struct Camera{
  int r,c,type;  
};

int N,M;
int Map[8][8];
vector<Camera> C_status;
int cam_run[5][5] = {//[][4] = 경우의 수
  {1,0,0,0,4}, {1,0,1,0,2},
  {1,1,0,0,4}, {1,1,1,0,4},
  {1,1,1,1,1}
};
//0 : 하, 1 : 좌, 2 : 상, 3 : 우
int Dr[4] = {1,0,-1,0};
int Dc[4] = {0,-1,0,1};

void move(int row, int col, int dir){
    //한쪽으로 전진하면서 감시하는 거 표시
    int nr = row + Dr[dir], nc = col + Dc[dir];
    if(nr < 0 || nc < 0 || nr > N-1 || nc > M-1) return;
    if(Map[nr][nc] == 6) return;
    
    Map[nr][nc] = 9;
    move(nr,nc,dir);
    
}

int solve(int cnt){
    if(cnt == C_status.size()){
        //마지막 카메라일 때
        //빈칸 갯수 세기
        int sum = 0;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < M; j++)
                if(Map[i][j] == 0)  sum++;
        return sum;
    }
    
    int res = INF;
    int backup[8][8];
    int n_type = C_status[cnt].type - 1;
    //0부터 사용하기때문에 -1
   
    for(int i = 0; i < cam_run[n_type][4]; i++){
        //원래 구조 카피해두기
        memcpy(backup, Map, sizeof(Map));
        for(int j = 0; j < 4; j++){
            //카메라가 활성화되어 있으면 감시함
            if(cam_run[n_type][j] == 1)
                move(C_status[cnt].r, C_status[cnt].c, (i+j)%4);
        }
        res = min(res, solve(cnt+1));
        memcpy(Map, backup, sizeof(Map));
    }

    return res;
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++){
            cin >> Map[i][j];
            if(Map[i][j] >= 1 && Map[i][j] <= 5)
                C_status.push_back({i,j,Map[i][j]});
        }
        
    cout << solve(0) << endl;
    
    return 0;
}