#define _CRT_SECURE_NO_WARNINGS #include typedef struct Cctv { int x; int y; }Cctv; Cctv cctv[8]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,-1,0 }; int n, m; int board1[10][10]; int board2[10][10]; void upd(int x, int y, int dir) { dir %= 4;//방향을 의미하기 때문에 4를 넘어가면 안됨 while (1) { x += dx[dir]; y += dy[dir]; if (x < 0 || x >= n || y < 0 || y >= m || board2[x][y] == 6) return; if (board2[x][y] != 0) continue; board2[x][y] = 7; } } int main() { scanf("%d %d", &n, &m); int mn = 0; int a = 0;//카메라 개수 for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { scanf("%d", &board1[i][j]); if (board1[i][j] != 0 && board1[i][j] != 6) { cctv[a].x = i; cctv[a++].y = j; } } } //밑이 2의 거듭제곱이면 비트연산자 사용하기 for (int tmp = 0;tmp < (1 << (2 * a));tmp++) { for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { board2[i][j] = board1[i][j]; } } int brute = tmp; for (int i = 0;i < a;i++) { int dir = brute % 4; brute /= 4; //4진수로 뽑아내는 과정 //방향이 4가지이기 때문에 4진수로 변환된 각 자리수가 각 카메라의 방향을 의미 int x = cctv[i].x; int y = cctv[i].y; if (board1[x][y] == 1) { upd(x, y, dir); } else if (board1[x][y] == 2) { if (dir == 2 || dir == 3) continue; upd(x, y, dir); upd(x, y, dir + 2); } else if (board1[x][y] == 3) { upd(x, y, dir); upd(x, y, dir + 1); } else if (board1[x][y] == 4) { upd(x, y, dir); upd(x, y, dir + 1); upd(x, y, dir + 2); } else { if (dir != 0) continue; upd(x, y, dir); upd(x, y, dir + 1); upd(x, y, dir + 2); upd(x, y, dir + 3); } } //시간복잡도의 최적화가 필요하면 각 카메라에서 겹치는 계산을 지워주기 int val = 0; for (int i = 0;i < n;i++) { for (int j = 0;j < m;j++) { if (board2[i][j] == 0) val++; } } mn = mn > val ? val : mn; } printf("%d", mn); return 0; }

제출 #16228

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: