#include //15683 typedef struct _camera { int x, y; } camera; int n, m, cam_n = 0; int map[10][10] = { 0 }, chk[10][10] = { 0 }; camera cam[10]; int map_coloring(int chked[][10], camera pos, int dir, int now); int main(void) { 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] == 2 || map[i][j] == 3 || map[i][j] == 4 || map[i][j] == 5) { cam[cam_n].x = i; cam[cam_n++].y = j; } } } // 1, 2, 3, 4 처리, BruteForce로 풀건데,, int dap = 100; if(cam_n == 0) { dap = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(map[i][j] != 6) ++dap; } } } else { for(int i = 0; i < cam_n; i++) { for(int j = 1; j <= 4; j++) { int tmp = map_coloring(chk, cam[i], j, 0); dap = dap < tmp ? dap : tmp; } } } printf("%d", dap); #if 0 // for debug printf("\n"); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) printf("%d ", chk[i][j]); printf("\n"); } printf("\n"); #endif return 0; } // 2는 사실상 2방향 // 1, 3, 4는 4방향 // 1 : 위, 2 : 아래, 3 : 왼쪽, 4 : 오른쪽으로 정의 int map_coloring(int origin[][10], camera pos, int dir, int now) { if(now == cam_n) { int cnt = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(origin[i][j] == 0 && map[i][j] != 6) ++cnt; } } return cnt; } int chked[10][10] = { 0 }; memcpy(chked, origin, sizeof(int) * 10 * 10); if(map[pos.x][pos.y] == 2) { if(dir == 2 || dir == 4) { for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } } else if(dir == 1 || dir == 3) { for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } } else if(map[pos.x][pos.y] == 5) { for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } else if(map[pos.x][pos.y] == 1) { if(dir == 1) { for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } } else if(dir == 2) { for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } } else if(dir == 3) { for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } else if(dir == 4) { for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } } else if(map[pos.x][pos.y] == 3) { if(dir == 1) { for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } else if(dir == 2) { for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } else if(dir == 3) { for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } else if(dir == 4) { for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } } else if(map[pos.x][pos.y] == 4) { if(dir == 1) { for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } } else if(dir == 2) { for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } else if(dir == 3) { for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } for(int i = pos.y; i >= 0; i--) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } } else if(dir == 4) { for(int i = pos.y; i < m; i++) { if(map[pos.x][i] == 6) break; chked[pos.x][i] = 1; } for(int i = pos.x; i >= 0; i--) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } for(int i = pos.x; i < n; i++) { if(map[i][pos.y] == 6) break; chked[i][pos.y] = 1; } } } #if 0 // for debug printf("\n"); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) printf("%d ", chked[i][j]); printf("\n"); } printf("\n"); #endif now++; int min = 100; for(int i = 1; i <= 4; i++) { int tmp = map_coloring(chked, cam[now], i, now); min = min < tmp ? min : tmp; } return min; }

제출 #29724

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: