import java.util.*; public class Main { static int[] di = {1, -1, 0, 0}; static int[] dj = {0, 0, 1, -1}; static int[][] map; static int N; static int M; static int max; static ArrayList lists = new ArrayList<>(); public static void main(String[] args) throws Exception { StringBuilder sb = new StringBuilder(); N = read(); M = read(); map = new int[N][M]; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { map[i][j] = read(); if(map[i][j] != 0 && map[i][j] != 6) { lists.add(new Integer[] {i, j, map[i][j]}); continue; } if(map[i][j] == 0) max++; } } if(lists.size() != 0)changeMap(0); System.out.println(max); } public static void changeMap(int idx) { if(idx == lists.size()) { int count = 0; for(int a = 0; a < N; a++) { for(int b = 0; b < M; b++) { if(map[a][b] == 0) count++; } } max = Math.min(count, max); return; } Integer[] arr = lists.get(idx); int i = arr[0]; int j = arr[1]; int val = arr[2]; if(val == 1) { for(int k = 0; k < 4; k++) { int ii = i + di[k]; int jj = j + dj[k]; // 시작 while(check(ii, jj)) { map[ii][jj]++; ii += di[k]; jj += dj[k]; } // 다음 changeMap(idx + 1); // 초기화 ii = i + di[k]; jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]--; ii += di[k]; jj += dj[k]; } } } else if(val == 2) { // 시작 for(int k = 0; k < 2; k++) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]++; ii += di[k]; jj += dj[k]; } } changeMap(idx + 1); // 초기화 for(int k = 0; k < 2; k++) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]--; ii += di[k]; jj += dj[k]; } } // 시작 for(int k = 2; k < 4; k++) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]++; ii += di[k]; jj += dj[k]; } } changeMap(idx + 1); // 초기화 for(int k = 2; k < 4; k++) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]--; ii += di[k]; jj += dj[k]; } } } else if(val == 4 ) { // 시작 for(int tmp = 0; tmp < 4; tmp++) { for(int k = 0; k < 4; k++) { if(tmp == k) continue; int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]++; ii += di[k]; jj += dj[k]; } } changeMap(idx + 1); // 초기화 for(int k = 0; k < 4; k++) { if(tmp == k) continue; int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]--; ii += di[k]; jj += dj[k]; } } } } else if(val == 3) { // 시작 for(int k = 0; k < 4; k+=2) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]++; ii += di[k]; jj += dj[k]; } } changeMap(idx + 1); // 초기화 for(int k = 0; k < 4; k+=2) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]--; ii += di[k]; jj += dj[k]; } } // 시작 for(int k = 1; k < 4; k+=2){ int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]++; ii += di[k]; jj += dj[k]; } } changeMap(idx + 1); // 초기화 for(int k = 1; k < 4; k+=2) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]--; ii += di[k]; jj += dj[k]; } } } else { // 시작 for(int k = 0; k < 4; k++) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]++; ii += di[k]; jj += dj[k]; } } changeMap(idx + 1); // 초기화 for(int k = 0; k < 4; k++) { int ii = i + di[k]; int jj = j + dj[k]; while(check(ii, jj)) { map[ii][jj]--; ii += di[k]; jj += dj[k]; } } } } public static boolean check(int i, int j) { return i >= 0 && i < N && j >= 0 && j < M && map[i][j] != 6; } private static int read() throws Exception { int d, o = 0; boolean negative = false; while ((d = System.in.read()) <= 32); if (d == '-') { negative = true; d = System.in.read(); } do { o = (o << 3) + (o << 1) + (d & 15); // o = o * 10 + (d - '0') } while ((d = System.in.read()) >= '0' && d <= '9'); return negative ? -o : o; } }

제출 #39938

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: