글 읽기 - [감시] 시작하자마자 틀렸습니다 뜹니다.. 반례나 틀린이유 부탁드립니다

rkddustn96 4년 전 0

브루스포스로 풀고있으며

벽과 cctv는 미리 전처리했습니다. 예제 testcase랑 질문글들에 있는 반례들은 다 옳게나옵니다 ㅠ

그후에 배열을 통해 cctv의 위치와 cctv종류를 저장해두고 순서대로 4방향을 검사하도록 코드를 짰습니다.

5번 cctv의 경우 바로 4방향을 감시하도록 했습니다.

visit의 경우 각각의 함수에 따른 temp_visit을 이용해 저장해두고 다른방향을 감시할때 원래visit을 불러와

원본으로 유지까지 잘 시켜뒀습니다 ㅠ

고수님들 도와주시면 감사하겠습니다.

#include <iostream>
#include <cstring>
using namespace std;

int Map[8][8];
int visit[8][8];

pair<int, int> cctvxy[8];
int cctv[8];

int cctvNum = 0;
int N, M, ans = 100;

void cctv_up(int xx, int yy) {
	while (1) {
		xx--;
		if (xx > -1 && Map[xx][yy] != 6) {
			visit[xx][yy] = true;
		}
		else
			return;
	}
}

void cctv_down(int xx, int yy) {
	while (1) {
		xx++;
		if (xx < N && Map[xx][yy] != 6) {
			visit[xx][yy] = true;
		}
		else
			return;
	}
}

void cctv_left(int xx, int yy) {
	while (1) {
		yy--;
		if (yy > -1 && Map[xx][yy] != 6) {
			visit[xx][yy] = true;
		}
		else
			return;
	}
}

void cctv_right(int xx, int yy) {
	while (1) {
		yy++;
		if (yy < M && Map[xx][yy] != 6) {
			visit[xx][yy] = true;
		}
		else
			return;
	}
}

void checctv(int xx, int yy, int cc, int dd) {
	switch (cc)
	{
	case 1:
		switch (dd)
		{
		case 1:
			cctv_right(xx, yy);
			break;
		case 2:
			cctv_down(xx, yy);
			break;
		case 3:
			cctv_left(xx, yy);
			break;
		case 4:
			cctv_up(xx, yy);
			break;
		}
		break;
	case 2:
		switch (dd)
		{
		case 1:
			cctv_right(xx, yy);
			cctv_left(xx, yy);
			break;
		case 2:
			cctv_up(xx, yy);
			cctv_down(xx, yy);
			break;
		case 3:
			cctv_right(xx, yy);
			cctv_left(xx, yy);
			break;
		case 4:
			cctv_up(xx, yy);
			cctv_down(xx, yy);
			break;
		}
		break;
	case 3:
		switch (dd)
		{
		case 1:
			cctv_up(xx, yy);
			cctv_right(xx, yy);
			break;
		case 2:
			cctv_right(xx, yy);
			cctv_down(xx, yy);
			break;
		case 3:
			cctv_down(xx, yy);
			cctv_left(xx, yy);
			break;
		case 4:
			cctv_left(xx, yy);
			cctv_up(xx, yy);
			break;
		}
		break;
	case 4:
		switch (dd)
		{
		case 1:
			cctv_left(xx, yy);
			cctv_up(xx, yy);
			cctv_right(xx, yy);
			break;
		case 2:
			cctv_up(xx, yy);
			cctv_right(xx, yy);
			cctv_down(xx, yy);
			break;
		case 3:
			cctv_right(xx, yy);
			cctv_down(xx, yy);
			cctv_left(xx, yy);
			break;
		case 4:
			cctv_down(xx, yy);
			cctv_left(xx, yy);
			cctv_up(xx, yy);
			break;
		}
		break;
	}
}

void brus(int ccstart) {
	int temp_visit[8][8];
	memcpy(temp_visit, visit, sizeof(visit));

	if (ccstart > cctvNum) {
		int temp_ans = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++) {
				if (!visit[i][j])
					temp_ans++;
			}
		ans = ans > temp_ans ? temp_ans : ans;
		return;
	}

	if (cctv[ccstart] == 5) {
		cctv_down(cctvxy[ccstart].first, cctvxy[ccstart].second);
		cctv_up(cctvxy[ccstart].first, cctvxy[ccstart].second);
		cctv_left(cctvxy[ccstart].first, cctvxy[ccstart].second);
		cctv_right(cctvxy[ccstart].first, cctvxy[ccstart].second);

		brus(ccstart + 1);
		memcpy(visit, temp_visit, sizeof(visit));
	}
	else
		for (int i = 0; i < 4; i++) {
			checctv(cctvxy[ccstart].first, cctvxy[ccstart].second, cctv[ccstart], i + 1);
			brus(ccstart + 1);
			memcpy(visit, temp_visit, sizeof(visit));
		}
}

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) {
				if (Map[i][j] == 6)
					visit[i][j] = true;
				else if (Map[i][j] > 0) {
					cctvxy[cctvNum] = { i,j };
					cctv[cctvNum] = Map[i][j];
					visit[i][j] = true;
					cctvNum++;
				}
			}
		}

	brus(0);

	cout << ans;

}

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

문제

문제

출처

ICPC

[감시] 시작하자마자 틀렸습니다 뜹니다.. 반례나 틀린이유 부탁드립니다

rkddustn96 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말