#include #include #define INF (~(1<<31)) #define MAX_NM 8 enum Map{ EMPTY = 0, WALL = 6, CCTV1 = 1, CCTV2 = 2, CCTV3 = 3, CCTV4 = 4, CCTV5 = 5, EAST = 0, SOUTH = 1, WEST = 2, NORTH = 3, }; typedef struct { int x; int y; }Pos; int N, M; char map[MAX_NM][MAX_NM]; // cctv int cctv_cnt = 0; Pos cctv_Arr[8]; int cctv_avb[6] = { 0,4,2,4,4,1 }; int cctv[5][4][4] = { { {1,0,0,0}, {0,1,0,0}, {0,0,1,0}, {0,0,0,1} // 8,4,2,1 }, { {1,0,1,0}, {0,1,0,1} // 10, 5 }, { {1,0,0,1}, {1,1,0,0}, {0,1,1,0}, {0,0,1,1} // }, { {1,0,1,1}, {1,1,0,1}, {1,1,1,0}, {0,1,1,1} }, { {1,1,1,1} }, }; int selected_dir[8]; int min_blind = INF; char temp_map[MAX_NM][MAX_NM] = { 0 }; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; void mark(Pos cur, Pos dxdy) { //temp_map[cur.x][cur.y] = '#'; Pos new = { cur.x + dxdy.x, cur.y + dxdy.y }; while (new.x >= 0 && new.x < N && new.y >= 0 && new.y < M && temp_map[new.x][new.y] != WALL) { //if (temp_map[new.x][new.y] == EMPTY) { // temp_map[new.x][new.y] = '#'; //} temp_map[new.x][new.y] = '#'; new.x += dxdy.x; new.y += dxdy.y; } } int calculate() { memcpy(temp_map, map, sizeof(temp_map)); for (int i = 0;i < cctv_cnt;i++) { Pos cur_cctv = cctv_Arr[i]; int type = map[cur_cctv.x][cur_cctv.y] - 1; int* rm_dir = cctv[type][selected_dir[i]]; //printf("%d : ", i); for (int j = EAST;j <= NORTH;j++) { //printf("%d ", rm_dir[i]); //printf("\n"); if (rm_dir[j] == 1) { Pos dxdy = { dx[j], dy[j] }; mark(cctv_Arr[i], dxdy); } } } int cnt = 0; for (int i = 0;i < N;i++) { for (int j = 0;j < M;j++) { if (temp_map[i][j] == EMPTY) { cnt++; } } } return cnt; } void makeCase(int cctv_idx) { if (cctv_idx == cctv_cnt) { // 거리 계산 int cur_blind = calculate(); //printf("cur : %d\n", cur_blind); if (cur_blind < min_blind) { min_blind = cur_blind; //for (int i = 0;i < cctv_cnt;i++) { // printf("%d ", selected_dir[i]); //} //printf("\n"); } return; } Pos cur_cctv = cctv_Arr[cctv_idx]; int type = map[cur_cctv.x][cur_cctv.y]; for (int i = 0;i < cctv_avb[type];i++) { // 방향 selected_dir[cctv_idx] = i; makeCase(cctv_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]); if (map[i][j] >= 1 && map[i][j] <= 5) { cctv_Arr[cctv_cnt++] = (Pos){ i,j }; } } } makeCase(0); printf("%d\n", min_blind); return 0; }

제출 #51396

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: