<C/C++> BOJ 15683 감시

15683번: 감시

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define INF ((int)1e9)
struct cctv { int r, c, num, dir; };
int N, M, ans;
int map[8][8];
static int dr[4] = { -1, 0, 1, 0 };
static int dc[4] = { 0, 1, 0, -1 };
vector<cctv> cctvs, cctv_5;

void CountZero() {
    int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) cnt++;
		}
	}
	ans = min(ans, cnt);
}

void Line(int r, int c, int dir) {
	int nr, nc, i = dir;
	nr = r + dr[i];
	nc = c + dc[i];

	for(;;) {
		if (nr < 0 || nr >= N || nc < 0 || nc >= M) break;
		if (map[nr][nc] == 0) map[nr][nc] = -1;
		else if (map[nr][nc] == 6) break;
		nr += dr[i];
		nc += dc[i];
	}
}

void Paint() {
	cctv tv;
	for (int i = 0; i < cctvs.size(); i++) {
		tv = cctvs[i];
		switch (tv.num) {
		case 1:
			Line(tv.r, tv.c, tv.dir);
			break;
		case 2:
			Line(tv.r, tv.c, tv.dir);
			Line(tv.r, tv.c, (tv.dir + 2) % 4);
			break;
		case 3:
			Line(tv.r, tv.c, tv.dir);
			Line(tv.r, tv.c, (tv.dir + 1) % 4);
			break;
		case 4:
			Line(tv.r, tv.c, tv.dir);
			Line(tv.r, tv.c, (tv.dir + 1) % 4);
			Line(tv.r, tv.c, (tv.dir + 2) % 4);
			break;
		}
	}
}
void monitor(int next) {
	if (next == cctvs.size()) {
		Paint();
		CountZero();
		return;
	}
	int temp[8][8];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			temp[i][j] = map[i][j];
		}
	}
	for (int d = 0; d < 4; d++) {
		cctvs[next].dir = d;
		monitor(next + 1);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = temp[i][j];
			}
		}
	}
}
void Solve() {
	cctv tv;
	for (int i = 0; i < cctv_5.size(); i++) {
		tv = cctv_5[i];
		Line(tv.r, tv.c, 0);
		Line(tv.r, tv.c, 1);
		Line(tv.r, tv.c, 2);
		Line(tv.r, tv.c, 3);
	}
	monitor(0);
	cout << ans << endl;
}
void InputData() {
	cin >> N >> M;

	cctv ncctv;
	ans = INF;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
			if (map[i][j] > 0 && map[i][j] < 5) {
				ncctv = { i, j, map[i][j], 0 };
				cctvs.push_back(ncctv);
			}
			else if (map[i][j] == 5) {
				ncctv = { i, j, map[i][j], 0 };
				cctv_5.push_back(ncctv);
			}
		}
	}
}

int main() {
	InputData();
	Solve();
	return 0;
}