import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] board, camera; static int n, m, answer; static boolean[][] visited; static int[] dx = { 1, 0, -1, 0 }; static int[] dy = { 0, -1, 0, 1 }; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); board = new int[n][m]; int cnt = 0; camera = new int[8][2]; visited = new boolean[n][m]; for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < m; j++) { int a = Integer.parseInt(st.nextToken()); if (a != 0) { board[i][j] = a; if(a == 6) { visited[i][j] = true; continue; } camera[cnt][0] = i; camera[cnt][1] = j; cnt++; } } } answer = n * m; dfs(cnt - 1); System.out.println(answer); } public static void spread(int dir, int x, int y) { while (board[x][y] != 6) { visited[x][y] = true; x += dx[dir]; y += dy[dir]; if (x >= n || x < 0 | y >= m || y < 0) break; } } public static void dfs(int cnt) { if (cnt < 0) { int blank = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!visited[i][j]) blank++; } } answer = Math.min(answer, blank); return; } boolean[][] nowv = new boolean[n][m]; for (int i = 0; i < n; i++) nowv[i] = visited[i].clone(); int nowx = camera[cnt][0]; int nowy = camera[cnt][1]; switch (board[nowx][nowy]) { case 1: for (int i = 0; i < 4; i++) { spread(i, nowx, nowy); dfs(cnt - 1); for (int j = 0; j < n; j++) visited[j] = nowv[j].clone(); } break; case 2: for (int i = 0; i < 2; i++) { spread(i, nowx, nowy); spread(i + 2, nowx, nowy); dfs(cnt - 1); for (int j = 0; j < n; j++) visited[j] = nowv[j].clone(); } break; case 3: for (int i = 0; i < 4; i++) { spread(i, nowx, nowy); spread((i + 1) % 4, nowx, nowy); dfs(cnt - 1); for (int j = 0; j < n; j++) visited[j] = nowv[j].clone(); } break; case 4: for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if (i != j) { spread(i, nowx, nowy); dfs(cnt - 1); for (int k = 0; k < n; k++) visited[k] = nowv[k].clone(); } } } break; case 5: for (int i = 0; i < 4; i++) { spread(i, nowx, nowy); } dfs(cnt - 1); for (int i = 0; i < n; i++) visited[i] = nowv[i].clone(); break; } } }

제출 #39882

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: