[BOJ 15683] 감시

BOJ::15683::감시

출처 : https://www.acmicpc.net/problem/15683

#include <bits/stdc++.h>

using namespace std;

int N, M, vs, a[8][8], ans,

dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, nc[6] = { 0,1,2,2,3,4 }, 

cc[6][4] = { {},{0},{0,2},{0,1},{0,1,3},{0,1,2,3} };

vector<pair<int, int>> v;

int cal(int vi, int res) {

if (vi == vs) return res;

int ta[8][8], tmp = 65; memcpy(ta, a, sizeof(a));

auto tp = v[vi];

for(int i=0;i<4;i++) {

int sdfsf = 1;

memcpy(a, ta, sizeof(ta)); int tr = res;

for(int j=0; j<nc[a[tp.first][tp.second]];j++) {

int jj = cc[a[tp.first][tp.second]][j];

int dd = (jj + i) % 4, ny = tp.first + dy[dd], nx = tp.second + dx[dd];

while (ny >= 0 && ny < N&&nx >= 0 && nx < M&&a[ny][nx] != 6) {

if (a[ny][nx] == 0) { a[ny][nx] = -1; tr--; }

ny += dy[dd]; nx += dx[dd];

}

}

tmp = min(tmp, cal((vi + 1),tr));

}

memcpy(a, ta, sizeof(ta));

return tmp;

}

int main() {

ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M;

for(int i=0; i<N; i++) for(int j=0; j<M; j++) {

cin >> a[i][j];

if (!a[i][j]) ans++;

else if (a[i][j] != 6) v.push_back(make_pair(i, j));

} vs = v.size();

cout << cal(0,ans);

return 0;

}