감시

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

15683번: 감시

#include <iostream>
#include <algorithm>
using namespace std;

struct CCTV{
	int type,y,x;
};

int n, m, ret=1000;
int map[8][8];
int cctv_size;
CCTV cctv[8];

int rot[5] = { 4,2,4,4,1 };

void mapCopy(int backup[8][8], int original[8][8]) {
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			backup[y][x] = original[y][x];
		}
	}
}

void update(int dir, CCTV cctv) {
	dir %= 4;
	if (dir == 0) {
		for (int x = cctv.x + 1; x < m; x++) {
			if (map[cctv.y][x] == 6) break;
			map[cctv.y][x] = -1; //카메라 감시 가능 = -1
		}
	}
	if (dir == 1) {
		for (int y = cctv.y - 1; y >= 0; y--) {
			if (map[y][cctv.x] == 6) break;
			map[y][cctv.x] = -1;
		}
	}
	if (dir == 2) {
		for (int x = cctv.x - 1; x >= 0; x--) {
			if (map[cctv.y][x] == 6) break;
			map[cctv.y][x] = -1;
		}
	}
	if (dir == 3) {
		for (int y = cctv.y + 1; y < n; y++) {
			if (map[y][cctv.x] == 6) break;
			map[y][cctv.x] = -1;
		}
	}

}

void dfs(int idx) {
	if (idx == cctv_size) {
		int check = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++) {
				if (map[y][x] == 0) check++;
			}
		}
		ret = min(ret, check);
		return;
	}
	else {
		int backup[8][8];
		int type = cctv[idx].type;
		for (int dir = 0; dir < rot[type]; dir++) {
			mapCopy(backup, map);
			if(type==0){ //카메라 종류
				update(dir, cctv[idx]);
			}
			if(type==1){
				update(dir, cctv[idx]);
				update(dir+2, cctv[idx]);
			}
			if(type==2){
				update(dir, cctv[idx]);
				update(dir+1, cctv[idx]);
				
			}
			if(type==3){
				update(dir, cctv[idx]);
				update(dir+1, cctv[idx]);
				update(dir+2, cctv[idx]);
			}
			if(type==4){
				update(dir, cctv[idx]);
				update(dir+1, cctv[idx]);
				update(dir+2, cctv[idx]);
				update(dir+3, cctv[idx]);
			}
			dfs(idx + 1);
			mapCopy(map, backup);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cin >> map[y][x];
			if (map[y][x] != 0 && map[y][x] != 6) {
				cctv[cctv_size].y = y;
				cctv[cctv_size].x = x;
				cctv[cctv_size].type = map[y][x]-1;
				cctv_size++;
			}
		}
	}
	dfs(0);
	cout << ret << "\n";
	return 0;
}