글 읽기 - 이거 반례하나 찾아주시면 리스펙트합니다...

junyoungwoo7 5년 전 0

질문게시판에 있는 반례, 예제 다 통과하는데 제출만 하면 틀리다고 뜨네요... 반례찾아주시거나 틀린점 찾아주시면 리스펙트하겠습니다 ㅠㅠㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct CCTV {
	int y, x, type;
};
int caseNum = 0;
int N, M, K;
int minValue = 987654321;
int office[8][8];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
vector<CCTV> cctvs;
void set(int y, int x, int dir,int delta) {
	int nextY = y + dy[dir];
	int nextX = x + dx[dir];
	while (!(nextY < 0 || nextX < 0 || nextY >= N || nextX >= M)&& office[nextY][nextX] != 6) {
		if (office[nextY][nextX] ==0 && delta == 1)
			office[nextY][nextX] = 7;
		else if(office[nextY][nextX] == 7 && delta == 1)
			office[nextY][nextX] = 8;
		else if (office[nextY][nextX] == 7 && delta == -1)
			office[nextY][nextX] = 0;
		else if (office[nextY][nextX] == 8 && delta == -1)
			office[nextY][nextX] = 7;
		nextY += dy[dir];
		nextX += dx[dir];
	}
}
void dfs(vector<CCTV> cctve) {
	//cctv 벡터를 돌면서 방향을 설정해준 후, 다른 방향으로 재귀호출한다.
	//1번의 경우 4가지, 2번의 경우 2가지, 3번도 4가지, 4번도 4가지, 5번 1가지
	if(!cctve.empty()) {
		CCTV cur = cctve.back();
		cctve.pop_back();
		if (cur.type == 1) {
			for (int dir = 0; dir < 4; dir++) {
				set(cur.y, cur.x, dir,1);
				dfs(cctve);
				set(cur.y, cur.x, dir, -1);
				
			}
			
		}
		else if (cur.type == 2) {
			//02 또는 13로 다채움
			
			for (int dir = 0; dir < 2; dir++) {
				set(cur.y, cur.x, dir, 1);
				set(cur.y, cur.x, dir+2, 1);
				dfs(cctve);
				set(cur.y, cur.x, dir, -1);
				set(cur.y, cur.x, dir + 2, -1);
			}
			
		}

		else if (cur.type == 3) {
			//01 12 23 34
			
			for (int dir = 0; dir < 4; dir++) {
				int temp = (dir + 1)%4;
				set(cur.y, cur.x, dir, 1);
				set(cur.y, cur.x, temp, 1);
				dfs(cctve);
				set(cur.y, cur.x, dir, -1);
				set(cur.y, cur.x, temp, -1);
			}
			
		}

		else if (cur.type == 4) {
			//012, 123, 230, 301
			
			for (int dir = 0; dir < 4; dir++) {
				int temp1 = (dir + 1)%4;
				int temp2 = (dir + 2)%4;
				set(cur.y, cur.x, dir, 1);
				set(cur.y, cur.x, temp1, 1);
				set(cur.y, cur.x, temp2, 1);
				
				dfs(cctve);
				set(cur.y, cur.x, dir, -1);
				set(cur.y, cur.x, temp1, -1);
				set(cur.y, cur.x, temp2, -1);
			}
		}
		else {
			for (int dir = 0; dir < 4; dir++) {
				set(cur.y, cur.x, dir, 1);
			}
			dfs(cctve);
		}
	}
	else {
		int cnt = 0;
		//cout << endl;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				//cout << office[i][j] << " ";
				if (office[i][j] == 0)
					cnt++;
			}
			//cout << endl;
		}
		caseNum++;
		minValue = min(minValue, cnt);
		//cout << "값 : " << minValue << endl;
		//cout << endl;
	}
	

}
int main() {
	cin >> N, cin >> M;
	for(int i=0;i<N;i++)
		for (int j = 0; j < M; j++) {
			cin >> office[i][j];
			if (office[i][j] != 0 && office[i][j] != 6) {
				CCTV temp;
				temp.y = i, temp.x = j, temp.type = office[i][j];
				cctvs.push_back(temp);
			}
		}
	dfs(cctvs);
	cout << minValue;
	//cout << caseNum << endl;
}

sait2000 5년 전 0

답은 아마 1인 것 같은데 2 나오네요

4
1 0 5
0 0 0

sait2000 5년 전 0

틀린 점은 아마 set에서 delta가 -1일 때 두 개 이상의 cctv가 보고 있는 칸을 지워버려서 그럴 거라고 봅니다.

junyoungwoo7 5년 전 0

말씀하신점 해결하니 되네요 !!! 감사합니다

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

문제

문제

출처

ICPC

이거 반례하나 찾아주시면 리스펙트합니다...

junyoungwoo7 5년 전 0

sait2000 5년 전 0

sait2000 5년 전 0

junyoungwoo7 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말