15683 감시

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

15683번: 감시

유형: 시뮬레이션

1. 한 방향만 보는 함수를 생성 see함수 생성

2. cctv 갯수만큼 재귀함수를 돌린다

3. cctv타입 마다 볼 수 있는 방법이 정해져 있음

int type_size[5] = {4,2,4,4,1};

예를 들면 타입0은 {동}{서}{남}{북} 전부 보는게 가능

타입1은 서로 {동서}, {남북} 자가지 경우의수 가능

이 처럼 위에 식대로 미리 크기를 정해 놓는다.

 

얼핏보면 dfs와 비슷해 보이지만 재귀를 빠져나갔을 경우 

다시 backup한 데이터로 map배열을 초기화 시켜줘야 한다.

이 점이 dfs와 다른 점이다.

/*
	사각지대 최소크기
	재귀사용
	큐 사용
	struct
		y,x,type
	main
		입력
			cctv.push
	sol
		if cnt==cctv갯수
			완전탐색
				ans <- -1갯수 최대값
			return

		for type별 경우의수
			backup = map
			1유형
				see(d, info)
			2유형
				see(d, info )
				see(d+2, info )
			...

			map = backup

		
	see
		d=d%4
		if d==0
			for
				if 벽 break
				map <- -1
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
struct INFO {
	int y, x, ty;
};
int N, M;
int map[8][8];
INFO info[8];
int tv_num;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int type_size[5] = {4,2,4,4,1};
int ans = 64;
void see(int d,int index) 
{
	int dir = d % 4;
	if (dir == 0)//북
	{
		for (int i = info[index].y; i >= 0; i--)
		{
			if (map[i][info[index].x] == 6 ) break;
			else if(map[i][info[index].x]==0)
				map[i][info[index].x] = -1;
		}
	}
	else if (dir == 1)//동
	{
		for (int i = info[index].x; i <M; i++)
		{
			if (map[info[index].y][i] == 6) break;
			else if (map[info[index].y][i] == 0)
				map[info[index].y][i] = -1;
		}
	}
	else if (dir == 2)//남
	{
		for (int i = info[index].y; i<N; i++)
		{
			if (map[i][info[index].x] == 6) break;
			else if (map[i][info[index].x] == 0)
				map[i][info[index].x] = -1;
		}
	}
	else if (dir == 3)//서
	{
		for (int i = info[index].x; i >=0; i--)
		{
			if (map[info[index].y][i] == 6) break;
			else if (map[info[index].y][i] == 0)
				map[info[index].y][i] = -1;
		}
	}
}
void sol(int index)
{
	if (index == tv_num)
	{
		int ret = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 0) ret++;
			}
		}
		ans = min(ans, ret);
		return;
	}
	for (int i = 0; i < type_size[info[index].ty];i++)
	{
		int backup[8][8];
		memcpy(backup, map, sizeof(map));
		if (info[index].ty == 0)
		{
			see(i,index);
		}
		else if (info[index].ty == 1)
		{
			see(i, index);
			see(i+2, index);
		}
		else if (info[index].ty == 2)
		{
			see(i, index);
			see(i+1, index);
		}
		else if (info[index].ty == 3)
		{
			see(i, index);
			see(i+1, index);
			see(i+2, index);
		}
		else if (info[index].ty == 4)
		{
			see(i, index);
			see(i+1, index);
			see(i+2, index);
			see(i+3, index);
		}
		sol(index + 1);
		memcpy(map, backup, sizeof(map));
	}
}
int main() {
	cin >> N >> M;
	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] != 6) {
				info[tv_num].y = i;
				info[tv_num].x = j;
				info[tv_num].ty = map[i][j]-1;
				tv_num++;
			}
		}
	}
	sol(0);
	cout << ans;
}