kingsubin

import java.io.*;
import java.util.*;
 
public class boj_15683 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1}; // 남동북서
    static int[][] map1 = new int[10][10];
    static int[][] map2 = new int[10][10];
    static List<int[]> cctv = new ArrayList<>();
    static int row, col, min;
 
    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
 
    static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
 
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map1[i][j] = Integer.parseInt(st.nextToken());
                if (map1[i][j] == 0) min++;
                if (map1[i][j] > 0 && map1[i][j] < 6) {
                    cctv.add(new int[]{i, j});
                }
            }
        }
    }
 
    static void solve() {
        for (int temp = 0; temp < (1 << (2 * cctv.size())); temp++) {
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    map2[i][j] = map1[i][j];
                }
            }
 
            int brute = temp;
            for (int[] now : cctv) {
                int dir = brute % 4;
                brute /= 4;
                int x = now[0];
                int y = now[1];
 
                switch (map1[x][y]) {
                    case 1:
                        upd(x, y, dir);
                        break;
                    case 2:
                        upd(x, y, dir);
                        upd(x, y, dir + 2);
                        break;
                    case 3:
                        upd(x, y, dir);
                        upd(x, y, dir + 1);
                        break;
                    case 4:
                        upd(x, y, dir);
                        upd(x, y, dir + 1);
                        upd(x, y, dir + 2);
                        break;
                    default:
                        upd(x, y, dir);
                        upd(x, y, dir + 1);
                        upd(x, y, dir + 2);
                        upd(x, y, dir + 3);
                }
            }
 
            int val = 0;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (map2[i][j] == 0) val++;
                }
            }
 
            min = Math.min(min, val);
        }
        System.out.println(min);
    }
 
    static boolean OOB(int x, int y) { // Out of Bounds
        return x < 0 || x >= row || y < 0 || y >= col;
    }
 
    static void upd(int x, int y, int dir) {
        dir %= 4;
        while (true) {
            x += dx[dir];
            y += dy[dir];
            if (OOB(x, y) || map2[x][y] == 6) return; // 범위 벗어나거나 벽 만나면
            if (map2[x][y] != 0) continue; // 빈칸이 아닐경우
            map2[x][y] = 7; // 7로 마킹
        }
    }
}
 
 

 

- 시뮬레이션

- 어렵다 ,,

 

- 1. cctv 최대 개숫가 8개니까 4^8 경우의 수로 전부 돌려서 그 중에 최솟값을 찾는법

- 2. cctv 1-2-3-4-5 순서로 돌리는 방법 

- 근데 다시 생각해보니까 2번은 말이 안된다. 맵을 돌면서 cctv를 발견하면 그때마다 가장 적합한 해를 찾는 방법으로 해도 맞지않고

결국엔 전부 동시에 cctv를 돌려야하고 가능한 방향수는 최대 4^8 -1 이니까 이걸 전부 돌려봐야한다.

 

1. 입력받을때 0의 수 체크, cctv는 list에 넣어준다.

2. 총 0 ~ 4^ cctv갯수 번 roof를 돈다. (temp)

3. 방향 조합의 수를 4진수라고 생각 (최대 4방향이니 0, 1, 2, 3 )

  10진수의 수에서 각 자리 뽑는것처럼 4진수도 똑같은 방법으로 뽑을 수 있음

4. upd() 는 매개변수로 들어온 방향으로 쭉 방문했다는 마킹을 남긴다. (벽, 범위 주의)

5. 1번 cctv는 단방향이니 upd(x, y, dir) 이런식인데 2,3,4 번의 경우 따로 처리해주어야 한다.

6. (temp) 루프에서 매번 map2에 마킹된것을 보고 0을 카운팅하고 최솟값을 계속 갱신해준다.

 

 

 

 

---

www.acmicpc.net/problem/15683