백준 : 15683*

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

15683번: 감시

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, M;
int Arr[8][8];
int min_v = 0x7f7f7f;
int vSize = 0;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
struct L {
	int y;
	int x;
};
vector <L> buffer;


void Draw(int y, int x, vector<L>& v, int d) {
	while (true) {
		y += dy[d];
		x += dx[d];
		if (y < 0 || x < 0 || y >= N || x >= M) break;
		if (Arr[y][x] == 6) break;
		if (Arr[y][x] != 0) continue;
		v.push_back({ y,x });
		Arr[y][x] = 7;
	}
}

void Clear(vector<L>& v) {
	L b;
	while (!v.empty()) {
		b = v.back();
		v.pop_back();

		Arr[b.y][b.x] = 0;
	}
}

int GetMin() {

	int myMin = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Arr[i][j] == 0) ++myMin;
		}
	}
	return myMin;
}

void DFS(int seq) {
	if (seq >= vSize) {
		min_v = min(min_v, GetMin());

		return;
	}

	int y = buffer[seq].y;
	int x = buffer[seq].x;
	vector<L> v;

	if (Arr[y][x] == 1) {
		for (int d = 0; d < 4; d++) {
			Draw(y, x, v, d);
			DFS(seq + 1);
			Clear(v);
		}
	}
	else if (Arr[y][x] == 2) {
		for (int d = 0; d < 2; d++) {
			Draw(y, x, v, d);
			Draw(y, x, v, d + 2);
			DFS(seq + 1);
			Clear(v);
		}
	}
	else if (Arr[y][x] == 3) {
		for (int d = 0; d < 4; d++) {
			Draw(y, x, v, d);
			Draw(y, x, v, (d + 1) % 4);
			DFS(seq + 1);
			Clear(v);
		}
	}
	else if (Arr[y][x] == 4) {
		for (int d = 1; d <= 4; d++) {
			Draw(y, x, v, d - 1);
			Draw(y, x, v, d % 4);
			Draw(y, x, v, (d + 1) % 4);
			DFS(seq + 1);
			Clear(v);
		}
	}
	else if (Arr[y][x] == 5) {
		Draw(y, x, v, 0);
		Draw(y, x, v, 1);
		Draw(y, x, v, 2);
		Draw(y, x, v, 3);
		DFS(seq + 1);
		Clear(v);
	}
}


int main(void) {
	cin >> N >> M;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> Arr[i][j];
			if (Arr[i][j] != 0 && Arr[i][j] != 6) {
				buffer.push_back({ i, j });
			}
		}
	}

	vSize = buffer.size();
	DFS(0);
	cout << min_v;

}