import java.io.*; import java.util.*; public class Main { private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); private static StringTokenizer st; private static void readLine() throws IOException { st = new StringTokenizer(br.readLine()); } private static int nextInt() { return Integer.parseInt(st.nextToken()); } private static void printAnswer() throws IOException { bw.flush(); bw.close(); br.close(); } private static final int[][][] CCTV = { { { 0 }, { 1 }, { 2 }, { 3 } }, { { 0, 1 }, { 2, 3 } }, { { 0, 2 }, { 0, 3 }, { 1, 2 }, { 1, 3 } }, { { 0, 1, 2 }, { 0, 1, 3 }, { 0, 2, 3 }, { 1, 2, 3 } }, { { 0, 1, 2, 3 } } }; private static final int[] dx = { 0, 0, -1, 1 }; private static final int[] dy = { 1, -1, 0, 0 }; private static int N, M, ans; private static int[][] mat; public static void main(String[] args) throws IOException { readLine(); N = nextInt(); M = nextInt(); mat = new int[N][M]; for (int i = 0; i < N; i++) { readLine(); for (int j = 0; j < M; j++) mat[i][j] = nextInt(); } dfs(0, mat); bw.write((N * M - ans) + "\n"); printAnswer(); } public static void dfs(int idx, int[][] matrix) { if (idx == N * M) { ans = Math.max(ans, count(matrix)); return; } int[][] tmp = new int[N][M]; for (int i = 0; i < N; i++) tmp[i] = matrix[i].clone(); int y = idx / M; int x = idx % M; if (tmp[y][x] < 1 || 5 < tmp[y][x]) dfs(idx + 1, tmp); else { for (int i = 0; i < CCTV[tmp[y][x] - 1].length; i++) { for (int k = 0; k < N; k++) tmp[k] = matrix[k].clone(); for (int j = 0; j < CCTV[tmp[y][x] - 1][i].length; j++) flip(y, x, CCTV[tmp[y][x] - 1][i][j], tmp); dfs(idx + 1, tmp); } } } public static void flip(int y, int x, int d, int[][] matrix) { while (!OOB(y += dy[d], x += dx[d], matrix)) { matrix[y][x] = -1; } } public static int count(int[][] matrix) { // printMatrix(matrix); int ret = 0; for (int[] row : matrix) for (int it : row) ret += it != 0 ? 1 : 0; return ret; } public static boolean OOB(int y, int x, int[][] matrix) { return (y < 0 || y >= N || x < 0 || x >= M || matrix[y][x] == 6); } public static void printMatrix(int[][] matrix) { for (int[] row : matrix) { for (int it : row) System.out.printf("%3d ", it); System.out.println(); } System.out.println(); } }

제출 #39926

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: