import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { static int N; static int M; static int[][] map; static int min; static List cctvs = new ArrayList<>(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); map = new int[N][M]; min = N * M; for (int y = 0; y < N; y++) { st = new StringTokenizer(br.readLine()); for (int x = 0; x < M; x++) { map[y][x] = Integer.parseInt(st.nextToken()); if (map[y][x] > 0 && map[y][x] < 5) { // 1,2,3,4번의 경우 cctv에 위치와 종류 저장 cctvs.add(new Integer[3]); cctvs.get(cctvs.size() - 1)[0] = y; cctvs.get(cctvs.size() - 1)[1] = x; cctvs.get(cctvs.size() - 1)[2] = map[y][x]; } if (map[y][x] == 5) { // 5번 CCTV는 네 방향 모두 감시 watch(y, x, -1, 0); // 위 watch(y, x, 1, 0); // 아래 watch(y, x, 0, -1); // 왼쪽 watch(y, x, 0, 1); // 오른쪽 } } } permu(0); System.out.println(min); } public static void permu(int index) { if (index == cctvs.size()) { int cnt = 0; for (int y = 0; y < N; y++) { for (int x = 0; x < M; x++) { if (map[y][x] == 0) cnt++; } } min = Math.min(min, cnt); return; } int y = cctvs.get(index)[0]; int x = cctvs.get(index)[1]; int type = cctvs.get(index)[2]; int[][] basemap = new int[map.length][]; for (int i = 0; i < map.length; i++) { basemap[i] = map[i].clone(); } switch (type) { case 1: left(y, x); permu(index + 1); revertmap(basemap); right(y, x); permu(index + 1); revertmap(basemap); up(y, x); permu(index + 1); revertmap(basemap); down(y, x); permu(index + 1); revertmap(basemap); break; case 2: left(y, x); right(y, x); permu(index + 1); revertmap(basemap); up(y, x); down(y, x); permu(index + 1); revertmap(basemap); break; case 3: left(y, x); up(y, x); permu(index + 1); revertmap(basemap); right(y, x); up(y, x); permu(index + 1); revertmap(basemap); left(y, x); down(y, x); permu(index + 1); revertmap(basemap); right(y, x); down(y, x); permu(index + 1); revertmap(basemap); break; case 4: left(y, x); right(y, x); up(y, x); permu(index + 1); revertmap(basemap); left(y, x); right(y, x); down(y, x); permu(index + 1); revertmap(basemap); break; } } public static void left(int y, int x) { for (int i = x; i >= 0; i--) { if (map[y][i] == 0) map[y][i] = -1; if (map[y][i] == 6) break; } } public static void right(int y, int x) { for (int i = x; i < M; i++) { if (map[y][i] == 0) map[y][i] = -1; if (map[y][i] == 6) break; } } public static void up(int y, int x) { for (int i = y; i >= 0; i--) { if (map[i][x] == 0) map[i][x] = -1; if (map[i][x] == 6) break; } } public static void down(int y, int x) { for (int i = y; i < N; i++) { if (map[i][x] == 0) map[i][x] = -1; if (map[i][x] == 6) break; } } public static void revertmap(int[][] basemap) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { map[i][j] = basemap[i][j]; // 깊은 복사 수행 } } } public static void watch(int y, int x, int dy, int dx) { int ny = y; int nx = x; while (true) { ny += dy; nx += dx; if (ny < 0 || ny >= N || nx < 0 || nx >= M || map[ny][nx] == 6) break; // 벽을 만나면 중단 if (map[ny][nx] == 0) map[ny][nx] = -1; // 감시 영역 표시 } } }

제출 #40184

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: