백준-감시.cpp.txt

#include <iostream>
#include<vector>
using namespace std;
vector<int> cctv_locate;
int arr[9][9];
int cctv_state[8];
int simulate_arr[9][9];
int N,M;
int ret = 10000;
int cctv_size;
void playing_cctv(int x, int y,int H)
{
	if (H == 1)
	{
		while (x - 1 >= 0 && simulate_arr[x - 1][y] != 6)
		{
			if (simulate_arr[x - 1][y] == 0)
				simulate_arr[x - 1][y] = -1;
			x--;
		}
	}//up
	else if (H == 2)
	{
		while (y + 1<M&&simulate_arr[x][y + 1] != 6)
		{
			if (simulate_arr[x][y + 1] == 0)
				simulate_arr[x][y + 1] = -1;
			y++;
		}
	}//right
	else if (H == 3)
	{
		while (y - 1 >= 0 && simulate_arr[x][y - 1] != 6)
		{
			if (simulate_arr[x][y - 1] == 0)
				simulate_arr[x][y - 1] = -1;
			y--;
		}
	}//left
	else if (H == 4)
	{
		while (x + 1<N&&simulate_arr[x + 1][y] != 6)
		{
			if (simulate_arr[x + 1][y] == 0)
				simulate_arr[x + 1][y] = -1;
			x++;
		}

	}//down
}
void simulate()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
			simulate_arr[i][j] = arr[i][j];
	}

	for (int i = 0; i < cctv_size; i++)
	{
		int x = cctv_locate[i] / M;
		int y = cctv_locate[i] % M;
		if (simulate_arr[x][y] == 1)
		{
			if (cctv_state[i] == 0)
			{
				playing_cctv(x, y, 2);
				//right
			}
			else if (cctv_state[i] == 1)
			{
				playing_cctv(x, y, 4);
				//down
			}
			else if (cctv_state[i] == 2)
			{
				playing_cctv(x, y, 3);
				//left
			}
			else if (cctv_state[i] == 3)
			{
				playing_cctv(x, y, 1);
				//up
			}
		}
		else if (simulate_arr[x][y] == 2)
		{
			if (cctv_state[i] == 0)
			{
				playing_cctv(x, y, 2);
				playing_cctv(x, y, 3);
			}
			else if (cctv_state[i] == 1)
			{
				playing_cctv(x, y, 1);
				playing_cctv(x, y, 4);
			}
		}
		else if (simulate_arr[x][y] == 3)
		{
			if (cctv_state[i] == 0)
			{
				playing_cctv(x, y, 1);
				playing_cctv(x, y, 2);
			}
			else if (cctv_state[i] == 1)
			{
				playing_cctv(x, y, 4);
				playing_cctv(x, y, 2);
			}
			else if (cctv_state[i] == 2)
			{
				playing_cctv(x, y, 3);
				playing_cctv(x, y, 4);
			}
			else if (cctv_state[i] == 3)
			{
				playing_cctv(x, y, 3);
				playing_cctv(x, y, 1);
			}
		}
		else if (simulate_arr[x][y] == 4)
		{
			if (cctv_state[i] == 0)
			{
				playing_cctv(x, y, 1);
				playing_cctv(x, y, 2);
				playing_cctv(x, y, 3);
			}
			else if (cctv_state[i] == 1)
			{
				playing_cctv(x, y, 1);
				playing_cctv(x, y, 3);
				playing_cctv(x, y, 4);
			}
			else if (cctv_state[i] == 2)
			{
				playing_cctv(x, y, 2);
				playing_cctv(x, y, 3);
				playing_cctv(x, y, 4);
			}
			else if (cctv_state[i] == 3)
			{
				playing_cctv(x, y, 1);
				playing_cctv(x, y, 4);
				playing_cctv(x, y, 2);
			}
		}
		else if (simulate_arr[x][y] == 5)
		{
			playing_cctv(x, y, 1);
			playing_cctv(x, y, 2);
			playing_cctv(x, y, 3);
			playing_cctv(x, y, 4);
		}
	}

	int count_c = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (simulate_arr[i][j] == 0)
				count_c++;
		}
	}
	if (count_c < ret)
		ret = count_c;
}

void make_cctv(int index)
{
	if (index == cctv_size)
	{
		simulate();
		return;
	}
	int x = cctv_locate[index] / M;
	int y = cctv_locate[index] % M;
	int cctv_case = arr[x][y];
	if (cctv_case == 1)
	{
		for (int i = 0; i < 4; i++)
		{
			cctv_state[index] = i;
			make_cctv(index + 1);
		}
	}
	else if (cctv_case == 2)
	{
		for (int i = 0; i < 2; i++)
		{
			cctv_state[index] = i;
			make_cctv(index + 1);
		}
	}
	else if (cctv_case == 3)
	{
		for (int i = 0; i < 4; i++)
		{
			cctv_state[index] = i;
			make_cctv(index + 1);
		}
	}
	else if (cctv_case == 4)
	{
		for (int i = 0; i < 4; i++)
		{
			cctv_state[index] = i;
			make_cctv(index + 1);
		}

	}
	else if (cctv_case == 5)
	{
			cctv_state[index] = 1;
			make_cctv(index + 1);
	}
}

int main()
{
	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)
			{
				cctv_locate.push_back(i*M + j);
			}
		}
	}	
	cctv_size = cctv_locate.size();	
	make_cctv(0);	
	cout << ret << endl;
	return 0;
}