글 읽기 - 반례를 도저히 못찾겠네요..

wiz9243 5년 전 0

F는 브루트포스를 하는 recurrence 과정 입니다. F1,2,3,4 는 각각 우,하,좌,상 순으로 감시카메라 가시범위를 체크한 겁니다.

node에 있는 mode는 타입이 뭐냐(1,2,3,4,5) x,y 는 좌표 dir은 방향입니다.

dir 예) mode=1 , dir=1 이면 F1만실행

mode=1, dir=2 이면 F2만 실행

벡터의 사이즈가 n개(cctv개수) 가 되었을 때 하나씩 꺼내면서 새로운 지도에 가시범위를 다 체크하고 cctv가 볼수 있는 총 개수를 num에 담습니다. 그리고 최대값(MAX)하고 비교합니다. 그래서 최종적으로 n*m에서 MAX를 빼서 사각지대의 최소값을 구하는 것입니다.

#include<iostream>
#include<vector>
using namespace std;
#define F v.push_back(tmp);func(cnt+1);v.pop_back();
#define F1 for (int j = v[k].y + 1; map[v[k].x][j] != 6 && j < m; j++) res[v[k].x][j] = 1
#define F2 for (int i = v[k].x + 1; map[i][v[k].y] != 6 && i < m; i++) res[i][v[k].y] = 1
#define F3 for (int j = v[k].y - 1; map[v[k].x][j] != 6 && j >= 0; j--) res[v[k].x][j] = 1
#define F4 for (int i = v[k].x - 1; map[i][v[k].y] != 6 && i >= 0; i--) res[i][v[k].y] = 1
struct node {
	int mode, x, y, dir;
};

int map[10][10];
vector<node> cctv;
vector<node> v;
int n, m, MAX;

void func(int cnt) {
	if (cnt == cctv.size()) {
		int res[10][10];
		for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++)res[i][j] = map[i][j];
		for (int k = 0; k < v.size(); k++) {
			if (v[k].mode == 1) {
				if (v[k].dir == 1) F1;
				else if (v[k].dir == 2) F2;
				else if (v[k].dir == 3) F3;
				else if (v[k].dir == 4) F4;
			}
			else if (v[k].mode == 2) {
				if (v[k].dir == 1) {
					F1; F3;
				}
				else if (v[k].dir == 2) {
					F2; F4;
				}
			}
			else if (v[k].mode == 3) {
				if (v[k].dir == 1) {
					F1; F2;
				}
				else if (v[k].dir == 2) {
					F2; F3;
				}
				else if (v[k].dir == 3) {
					F3; F4;
				}
				else if (v[k].dir == 4) {
					F4; F1;
				}
			}
			else if (v[k].mode == 4) {
				if (v[k].dir == 1) {
					F4; F1; F2;
				}
				else if (v[k].dir == 2) {
					F1; F2; F3;
				}
				else if (v[k].dir == 3) {
					F2; F3; F4;
				}
				else if (v[k].dir == 4) {
					F3; F4; F1;
				}
			}
			else if (v[k].mode == 5) {
				F1; F2; F3; F4;
			}
		}
		int num = 0;
		for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)if (res[i][j])num++;
		MAX = MAX > num ? MAX : num;
		return;
	}

	node tmp = cctv[cnt];
	if (tmp.mode == 1) {
		for (int i = 1; i < 5; i++) {
			tmp.dir = i;
			F;
		}
	}
	else if (tmp.mode == 2) {
		for (int i = 1; i < 3; i++) {
			tmp.dir = i;
			F;
		}
	}
	else if (tmp.mode == 3) {
		for (int i = 1; i < 5; i++) {
			tmp.dir = i;
			F;
		}
	}
	else if (tmp.mode == 4) {
		for (int i = 1; i < 5; i++) {
			tmp.dir = i;
			F;
		}
	}
	else if (tmp.mode == 5) {
		tmp.dir = 1;
		F;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {
		scanf("%d", &map[i][j]);
		if (map[i][j] != 0 && map[i][j] != 6)cctv.push_back({ map[i][j],i,j });
	}
	func(0);
	cout << n*m - MAX;
}

betain24 5년 전 1

i < m 을 i < n으로 바꾸면됩니다..

#define F2 for (int i = v[k].x + 1; map[i][v[k].y] != 6 && i < m; i++) res[i][v[k].y] = 1

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 도저히 못찾겠네요..

wiz9243 5년 전 0

betain24 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말