6130 : 감시 카메라
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
세로 N, 가로 M 크기의 격자 공간에 감시 카메라(CCTV)가 설치되어 있습니다. CCTV는 5가지 종류가 있습니다.
- 1번: 한쪽 방향만 감시
- 2번: 서로 반대되는 두 방향 감시
- 3번: 직각 방향의 두 방향 감시
- 4번: 세 방향 감시
- 5번: 네 방향 모두 감시
CCTV는 벽(6)을 뚫고 감시할 수 없으며, CCTV가 설치된 다른 칸은 통과하여 감시할 수 있습니다. CCTV의 방향을 적절히 회전하여 사각지대(CCTV가 감시할 수 없는 빈칸 0의 개수)의 최소 크기를 구하는 프로그램을 작성하십시오.
- 1번: 한쪽 방향만 감시
- 2번: 서로 반대되는 두 방향 감시
- 3번: 직각 방향의 두 방향 감시
- 4번: 세 방향 감시
- 5번: 네 방향 모두 감시
CCTV는 벽(6)을 뚫고 감시할 수 없으며, CCTV가 설치된 다른 칸은 통과하여 감시할 수 있습니다. CCTV의 방향을 적절히 회전하여 사각지대(CCTV가 감시할 수 없는 빈칸 0의 개수)의 최소 크기를 구하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 세로 크기 N과 가로 크기 M (1 ≤ N, M ≤ 8)이 주어집니다.
둘째 줄부터 N개의 줄에 격자 정보가 주어집니다. (0: 빈칸, 6: 벽, 1~5: CCTV 타입)
둘째 줄부터 N개의 줄에 격자 정보가 주어집니다. (0: 빈칸, 6: 벽, 1~5: CCTV 타입)
출력 설명
얻을 수 있는 최소 사각지대의 크기를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
20도움
CCTV의 최대 개수가 8개 이하이므로, DFS 백트래킹을 사용하여 각 CCTV의 방향을 하나씩 설정하고 감시 구역을 체크해 나가는 완전 탐색 기법으로 해결할 수 있습니다.