15683監視

質問リンク

コードの説明

監視カメラの種類を入力した後、それぞれの種類の数字をすべて算出する問題です.問題に入る前に、私たちはまず最悪のcaseを計算することに慣れて、完全に探求しているのか、それともタイムアウトしないのかを見てみましょう.
4^8*64で、400万くらいなので、1秒でできます.
次に、各モニタが閲覧できる方向数(便利!)を含む配列を作成します.
rotate_arr[]={4,2,4,4,1};
これは完全プローブにおけるタイプ分岐個数です
find()関数を作成し、壁に遭遇する前にすべてナビゲート(#)する方向をパラメータとして受け入れます.
方向に関数を呼び出す(コード注記を参照)

コード#コード#

#include<iostream>
#include<vector>
using namespace std;
struct CCTV {
	int type; //0,1,2,3
	int y;
	int x;
};
CCTV cctv[8];
int map[8][8];
int answer = 1000;
int N, M;
int K; //CCTV 개수
int rotate_arr[] = { 4,2,4,4,1 }; //type별 총 회전가능 횟수

void find(int dir, CCTV cctv) { // 한방향 모두 탐색하는 함수
	dir = dir % 4;

	if (dir == 0) {//동쪽 끝까지
		for (int i = cctv.x + 1; i < M; i++) {
			if (map[cctv.y][i] == 6) break;
			map[cctv.y][i] = -1; //-1로 탐색 완료 표시 (#)
		}
	}
	if (dir == 1) { //북쪽
		for (int i = cctv.y - 1; i >= 0; i--) {
			if (map[i][cctv.x] == 6) break;
			map[i][cctv.x] = -1; 
		}
	}
	if (dir == 2) { //서쪽
		for (int i = cctv.x - 1; i >= 0; i--) {
			if (map[cctv.y][i] == 6) break;
			map[cctv.y][i] = -1;
		}
	}
	if (dir == 3) { //남쪽
		for (int i = cctv.y + 1; i < N; i++) {
			if (map[i][cctv.x] == 6) break;
			map[i][cctv.x] = -1;
		}
		
	}


}


void dfs(int level) {
	if (level == K) {
		int cnt = 0;//사각지대크기 count
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				if (map[y][x] == 0) cnt++;
			}
		}
		answer = min(answer, cnt);
		return;
	}
	int backup[8][8];
	int type = cctv[level].type;
	for (int i = 0; i < rotate_arr[type]; i++) { //각 cctv type별로 탐색
		memcpy(backup, map, sizeof(map)); //map을 backup복사
		if (type == 0) { //한방향만 탐색
			find(i, cctv[level]);
		
		}
		else if (type == 1) {//두방향탐색
			find(i, cctv[level]);
			find(i+2, cctv[level]);
		}
		else if (type == 2) { //두방향
			find(i, cctv[level]);
			find(i+1, cctv[level]);
			
		}
		else if (type == 3) { //세방향
			find(i, cctv[level]);
			find(i + 1, cctv[level]);
			find(i + 2, cctv[level]);
		}
		else if (type == 4) { //네방향
			find(i, cctv[level]);
			find(i + 1, cctv[level]);
			find(i + 2, cctv[level]);
			find(i + 3, cctv[level]);
		}
		dfs(level + 1);
		memcpy(map, backup, sizeof(backup)); //탐색완료후 backup-> map복사 (완전탐색을 위해 한단계 탐색이후 돌아올때 그전 map상태 저장)
	}
}
int main() {
	cin >> N >> M;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
			if (map[y][x] != 0 && map[y][x] != 6) {
				cctv[K].y = y;
				cctv[K].x = x;
				cctv[K].type = map[y][x] - 1;
				K++;
			}
		}
	}
	dfs(0);
	cout << answer;
	return 0;
}