[BOJ] 15683 : 감시

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
const int R = 1, D = 2, L = 4, U = 8;
vector<int> sight[6] = { {},
    { R,D,L,U },
    { L+R,U+D },
    { R+D,D+L,L+U,U+R },
    { R+D+L,D+L+U,L+U+R,U+R+D },
    { R+D+L+U }
};

int n, m;
int a[10][10], b[10][10];
struct abc { int x, y; };
vector<abc> cam;

inline void paint(int x, int y, int dir, int dif) {
    b[x][y] += dif;
    while (a[x][y] != 6) {
        x += dx[dir], y += dy[dir];
        b[x][y] += dif;
    }
}

int gogo(int cnum) {
    int x = cam[cnum].x, y = cam[cnum].y;
    int cdir = a[x][y];

    if (cnum == cam.size()) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (!b[i][j]) cnt++;
            }
        }
        return cnt;
    }

    int ret = 1e9;
    for (int sgt : sight[cdir]) {
        for (int i = 0; i < 4; i++) {
            if (sgt & (1<<i)) paint(x, y, i, +1);
        }
        ret = min(ret, gogo(cnum+1));
        for (int i = 0; i < 4; i++) {
            if (sgt & (1<<i)) paint(x, y, i, -1);
        }
    }

    return ret;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            if (1 <= a[i][j] && a[i][j] <= 5) cam.push_back({ i,j });
            if (a[i][j] == 6) b[i][j] = 1;
        }
    }
    for (int i = 0; i <= n+1; i++) a[i][0] = a[i][m+1] = 6;
    for (int i = 0; i <= m+1; i++) a[0][i] = a[n+1][i] = 6;
    
    printf("%d", gogo(0));

    return 0;
}