import java.util.*; import java.io.*; public class Main { static int N, M, li[][], ans; static ArrayList cs; 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()); li = new int[N][M]; cs = new ArrayList<>(); ans = 123123123; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) { li[i][j] = Integer.parseInt(st.nextToken()); if (li[i][j] >= 1 && li[i][j] <= 5) { cs.add(new Pair(i, j, li[i][j])); } } } find(0); System.out.println(ans); } static void find(int n) { if (n == cs.size()) { int local = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M ; j++) { local += li[i][j] == 0 ? 1 : 0; } } ans = Math.min(local, ans); return; } Pair p = cs.get(n); int[][][] ds = p.ds(); for (int i = 0; i < ds.length; i++) { for (int j = 0; j < ds[0].length; j++) { int x = p.x + ds[i][j][0]; int y = p.y + ds[i][j][1]; while ((x >= 0 && y >= 0 && x < N && y < M) && li[x][y] != 6) { if (li[x][y] == 0) { li[x][y] += 7; } x += ds[i][j][0]; y += ds[i][j][1]; } } find(n + 1); for (int j = 0; j < ds[0].length; j++) { int x = p.x + ds[i][j][0]; int y = p.y + ds[i][j][1]; while ((x >= 0 && y >= 0 && x < N && y < M) && (li[x][y] > 6)) { li[x][y] -= 7; x += ds[i][j][0]; y += ds[i][j][1]; } } } } static class Pair { int x,y, d; public Pair(int x, int y, int d) { this.x = x; this.y = y; this.d = d; } int[][][] ds() { if (d == 1) { return new int[][][]{{{0, 1}}, {{1, 0}}, {{0, -1}}, {{-1, 0}}}; } else if (d == 2) { return new int[][][]{{{0, 1}, {0, -1}}, {{1, 0}, {-1, 0}}}; } else if (d == 3) { return new int[][][]{{{0, 1}, {1, 0}}, {{0, 1}, {-1, 0}}, {{0, -1}, {1, 0}}, {{0, -1}, {-1, 0}}}; } else if (d == 4) { return new int[][][]{{{0, 1}, {1, 0}, {-1, 0}}, {{0, -1}, {-1, 0}, {1, 0}}, {{0, 1}, {1, 0}, {0, -1}}, {{0, -1}, {-1, 0}, {0, 1}}}; } else { return new int[][][]{{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}}; } } } }

제출 #194469

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: