감시 (feat.백준, 15683번)

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

15683번: 감시

반응형

// woohyeon.kim
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct CameraPosition
{
	int x;
	int y;
	int type;
};

int N, M;
int dx[4], dy[4];			// 0 : 북, 1 : 동, 2 : 남, 3 : 서
int arr[9][9];
CameraPosition cameras[9];
int cameras_count;
int result;

inline void copy(int (*dst)[9], int (*src)[9])
{
	for (auto ix = 0; ix < N; ++ix)
		for (auto iy = 0; iy < M; ++iy)
			dst[ix][iy] = src[ix][iy];
}

inline void start_watch(int x, int y, const int& direction, int (*tmp)[9])
{
	if(direction == 0 || direction == 2)
		x = x + dx[direction];
	else
		y = y + dy[direction];

	if (0 <= x && x < N && 0 <= y && y < M && tmp[x][y] != 6)
	{
		if (tmp[x][y] == 0)
			tmp[x][y] = 7;
		start_watch(x, y, direction, tmp);
	}
}

inline const int get_count_zero(int (*tmp)[9])
{
	auto count = 0;
	for (auto ix = 0; ix < N; ++ix)
		for (auto iy = 0; iy < M; ++iy)
			if (tmp[ix][iy] == 0)
				++count;
	return count;
}

inline void dfs(int index, int (*tmp)[9])
{
	int copy_arr[9][9];
	for (auto idx = index; idx < cameras_count; ++idx)
	{
		auto& camera = cameras[idx];
		if (camera.type == 1)
		{
			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 0, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 1, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 2, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 3, copy_arr);
			dfs(idx + 1, copy_arr);
			return;
		}
		else if (camera.type == 2)
		{
			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 0, copy_arr);
			start_watch(camera.x, camera.y, 2, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 1, copy_arr);
			start_watch(camera.x, camera.y, 3, copy_arr);
			dfs(idx + 1, copy_arr);
			return;
		}
		else if (camera.type == 3)
		{
			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 0, copy_arr);
			start_watch(camera.x, camera.y, 1, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 1, copy_arr);
			start_watch(camera.x, camera.y, 2, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 2, copy_arr);
			start_watch(camera.x, camera.y, 3, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 3, copy_arr);
			start_watch(camera.x, camera.y, 0, copy_arr);
			dfs(idx + 1, copy_arr);
			return;
		}
		else if (camera.type == 4)
		{
			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 0, copy_arr);
			start_watch(camera.x, camera.y, 1, copy_arr);
			start_watch(camera.x, camera.y, 2, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 1, copy_arr);
			start_watch(camera.x, camera.y, 2, copy_arr);
			start_watch(camera.x, camera.y, 3, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 2, copy_arr);
			start_watch(camera.x, camera.y, 3, copy_arr);
			start_watch(camera.x, camera.y, 0, copy_arr);
			dfs(idx + 1, copy_arr);

			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 3, copy_arr);
			start_watch(camera.x, camera.y, 0, copy_arr);
			start_watch(camera.x, camera.y, 1, copy_arr);
			dfs(idx + 1, copy_arr);
			return;
		}
		else
		{
			copy(copy_arr, tmp);
			start_watch(camera.x, camera.y, 0, copy_arr);
			start_watch(camera.x, camera.y, 1, copy_arr);
			start_watch(camera.x, camera.y, 2, copy_arr);
			start_watch(camera.x, camera.y, 3, copy_arr);
			dfs(idx + 1, copy_arr);
			return;
		}
	}

	result = min(result, get_count_zero(tmp));
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = -1, dx[1] = 0, dx[2] = 1, dx[3] = 0;
	dy[0] = 0, dy[1] = 1, dy[2] = 0, dy[3] = -1;

	cameras_count = 0;
	cin >> N >> M;
	for (auto ix = 0; ix < N; ++ix)
	{
		for (auto iy = 0; iy < M; ++iy)
		{
			cin >> arr[ix][iy];
			if (1 <= arr[ix][iy] && arr[ix][iy] <= 5)
				cameras[cameras_count].x = ix, cameras[cameras_count].y = iy, cameras[cameras_count].type = arr[ix][iy], ++cameras_count;
		}
	}

	result = static_cast<int>(1e9);
	dfs(0, arr);
	cout << result << endl;
	
	return 0;
}
// *&)*@*