글 읽기 - 반례를 못 찾겠습니다.

pinb 5년 전 0

주어진 예시는 다 통과하는데 뭐가 문제일까요;;

#include <iostream>
#define MAX 9

using namespace std;

class Point{
public:
	int _x;
	int _y;
	int _type;

	Point(){};
	Point(int x, int y, int t){
		_x = x;
		_y = y;
		_type = t;
	};
};

enum Dir{ NONE = (1 << 0), WALL = (1 << 1), CAMERA = (1 << 2), UP = (1 << 3), DOWN = (1 << 4), LEFT = (1 << 5), RIGHT = (1 << 6) };
int check[MAX][MAX];
Point *ptCCTV = new Point[8];
int N, M;
int cctv_size = 0;
int minSize = MAX * MAX;

int Count(){
	int cnt = 0;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			if (check[i][j] == NONE){
				cnt++;
			}
		}
	}
	return cnt;
}

void Draw(int x, int y, Dir d, char c){
	if (d & UP){
		for (int i = x - 1; i >= 0; i--){
			if (check[i][y] & WALL){
				break;
			}

			if (c == '#'){
				check[i][y] |= UP;
			}
			else if (c == '0'){
				check[i][y] &= ~UP;
			}
		}
	}

	if (d & DOWN){
		for (int i = x + 1; i < MAX; i++){
			if (check[i][y] & WALL){
				break;
			}

			if (c == '#'){
				check[i][y] |= DOWN;
			}
			else if (c == '0'){
				check[i][y] &= ~DOWN;
			}
		}
	}

	if (d & LEFT){
		for (int i = y - 1; i >= 0; i--){
			if (check[x][i] & WALL) {
				break;
			}

			if (c == '#'){
				check[x][i] |= LEFT;
			}
			else if (c == '0'){
				check[x][i] &= ~LEFT;
			}
		}
	}

	if (d & RIGHT){
		for (int i = y + 1; i < MAX; i++){
			if (check[x][i] & WALL){
				break;
			}

			if (c == '#'){
				check[x][i] |= RIGHT;
			}
			else if (c == '0'){
				check[x][i] &= ~RIGHT;
			}
		}
	}
}

void Go(int s){
	if (s == cctv_size){
		int cnt = Count();
		if (cnt < minSize){
			minSize = cnt;
		}
		return;
	}

	switch (ptCCTV[s]._type){
	case 1:
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, UP, '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, UP, '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, DOWN, '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, DOWN, '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, LEFT, '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, LEFT, '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, RIGHT, '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, RIGHT, '0');
		break;

	case 2:
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | DOWN), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | DOWN), '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(LEFT | RIGHT), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(LEFT | RIGHT), '0');
		break;

	case 3:
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | RIGHT), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | RIGHT), '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(RIGHT | DOWN), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(RIGHT | DOWN), '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(DOWN | LEFT), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(DOWN | LEFT), '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(LEFT | UP), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(LEFT | UP), '0');
		break;

	case 4:
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(LEFT | UP | RIGHT), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(LEFT | UP | RIGHT), '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | RIGHT | DOWN), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | RIGHT | DOWN), '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(RIGHT | DOWN | LEFT), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(RIGHT | DOWN | LEFT), '0');

		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(DOWN | LEFT | UP), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(DOWN | LEFT | UP), '0');
		break;

	case 5:
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | DOWN | LEFT | RIGHT), '#');
		Go(s + 1);
		Draw(ptCCTV[s]._x, ptCCTV[s]._y, (Dir)(UP | DOWN | LEFT | RIGHT), '0');
		break;
	}
}

int main(){
	cin >> N >> M;

	for (int i = 0; i < N; i++){
		for (int j = 0; j < M; j++){
			int n;
			cin >> n;

			if (n == 0){
				check[i][j] = NONE;;
			}
			else if (n == 6){
				check[i][j] = WALL;
			}
			else{
				check[i][j] = CAMERA;
				ptCCTV[cctv_size++] = Point(i, j, n);
			}
		}
	}

	Go(0);
	cout << minSize << endl;

	return 0;
}

jh05013 5년 전 0

이렇게 설명 하나 없이 긴 코드는 아무도 읽을 엄두를 안 낼 것입니다. 각 변수가 뭐고 무슨 식을 사용해서 풀었는지 정도는 설명해 주세요.

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

문제

문제

출처

ICPC

반례를 못 찾겠습니다.

pinb 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말