BOJ_15683 : 감시

문제

스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.(이하생략)

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int n, m;
int ans = 64;

void scan(vector< vector<int> >& a, int x, int y, int k) {
	while (1) {
		x = x + dx[k];
		y = y + dy[k];

		if (x < 0 || x >= n || y < 0 || y >= m) break;
		if (a[x][y] == 0) {
			a[x][y] = 7;
		}
		else if (a[x][y] == 6) {
			break;
		}
		else {
			continue;
		}
	}
}

void ok(vector< vector<int> > a) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 0)
				cnt++;
		}
	}
	if (ans > cnt) ans = cnt;
}

void go(vector< vector<int> > a, vector< vector<bool> > check) {

	for ( int i=0 ; i < n; i++) {
		for ( int j = 0 ; j < m; j++) {
			if (check[i][j] == true) continue;
			check[i][j] = true;
			vector< vector<int> > na;
			if (a[i][j] == 1) {
				for (int k = 0; k < 4; k++) {
					na = a;
					scan(na, i, j, k);
					go(na, check);

				}
			}
			else if (a[i][j] == 2) {
				for (int k = 0; k < 2; k++) {
					na = a;
					scan(na, i, j, k);
					scan(na, i, j, k + 2);
					go(na, check);
				}
			}
			else if (a[i][j] == 3) {
				for (int k = 0; k < 3; k++) {
					na = a;
					scan(na, i, j, k);
					scan(na, i, j, k + 1);
					go(na, check);

				}
				na = a;
				scan(na, i, j, 0);
				scan(na, i, j, 3);
				go(na, check);
			}
			else if (a[i][j] == 4) {
				for (int k = 0; k < 4; k++) {
					na = a;
					scan(na, i, j, k%4);
					scan(na, i, j, (k + 1) %4);
					scan(na, i, j, (k + 2) % 4);
					go(na, check);

				}
			}
			else if (a[i][j] == 5) {
				na = a;
				for (int k = 0; k < 4; k++) {				
					scan(na, i, j, k);
				}
				go(na, check);
			}

		}
	}

	ok(a);
}


int main() {
	cin >> n >> m;
	vector< vector<int> > a(n, vector<int>(m));
	vector< vector<bool> > check(n, vector<bool>(m));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	go(a, check);
	cout << ans << '\n';

	return 0;
}