글 읽기 - [C]질문글들의 모든 반례가 다 맞습니다...ㅠ

qmdlrbwls 5년 전 0

see 함수와 unsee함수를 만들어서

see 는 +=1을 해줬고

unsee는 -=1을 해줬습니다.

어차피 6을 만날시엔 멈추고

다른 cctv를 만나도 +,-연산을해도 사각지대체크하는덴 무리가 없다 생각하여 짯습니다.

모든 반례가 다맞습니다... 근데 왜틀릴까요.. 정말 1시간 넘게 고민했습니다 ㅠ

#include <iostream>
using namespace std;
//19:45
int n, m, num, result = 2000000000;
int map[9][9];
int ch[9][9];
int dx[] = { 0,-1,0,1 };//좌,상,우,하
int dy[] = { -1,0,1,0 };
struct Camera {
	int dir;
	int x;
	int y;
}camera[9];
void see(int dir, int x, int y) {//CCTV가 보는 방향
	while (1) {//좌,상,우,하
		x += dx[dir];
		y += dy[dir];
		if (x >= 0 && y >= 0 && x < n&&y < m&&map[x][y] != 6) {
			ch[x][y] += 1;
		}
		else break;
	}
}
void unsee(int dir, int x, int y) {//dfs해제 이후 CCTV가 다시 안볼때
	while (1) {//0,1,2,3
		x += dx[dir];
		y += dy[dir];
		if (x >= 0 && y >= 0 && x < n&&y < m&&map[x][y] != 6) {
			ch[x][y] -= 1;
		}
		else break;
	}
}
void dfs(int dir, int x, int y, int cnt) {
	if (cnt == num) {
		int blind = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (ch[i][j] == 0) blind++;//사각지대 카운트
			}
		}
		result = result < blind ? result : blind;
		return;
	}
	if (dir == 1) {
		for (int i = 0; i < 4; i++) {
			see(i, x, y);
			dfs(camera[cnt + 1].dir, camera[cnt + 1].x, camera[cnt + 1].y, cnt + 1);
			unsee(i, x, y);
		}
	}
	else if (dir == 2) {
		for (int i = 0; i < 2; i++) {
			see(i, x, y);
			see(i + 2, x, y);
			dfs(camera[cnt + 1].dir, camera[cnt + 1].x, camera[cnt + 1].y, cnt + 1);
			unsee(i, x, y);
			unsee(i + 2, x, y);
		}
	}
	else if (dir == 3) {
		for (int i = 0; i < 4; i++) {
			see(i, x, y);
			see((i + 1) % 4, x, y);
			dfs(camera[cnt + 1].dir, camera[cnt + 1].x, camera[cnt + 1].y, cnt + 1);
			unsee(i, x, y);
			unsee((i + 1) % 4, x, y);
		}
	}
	else if (dir == 4) {
		for (int i = 0; i < 4; i++) {
			see(i, x, y);
			see((i + 1) % 4, x, y);
			see((i + 2) % 4, x, y);
			dfs(camera[cnt + 1].dir, camera[cnt + 1].x, camera[cnt + 1].y, cnt + 1);
			unsee(i, x, y);
			unsee((i + 1) % 4, x, y);
			unsee((i + 2) % 4, x, y);
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	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) {
				ch[i][j] = map[i][j];
			}
			if (map[i][j] >= 1 && map[i][j] < 5) {
				camera[num].dir = map[i][j];
				camera[num].x = i;
				camera[num].y = j;
				num++;
			}
			else if (map[i][j] == 5) {//5는 방향 상관없으니까 그냥 고정
				see(0, i, j);
				see(1, i, j);
				see(2, i, j);
				see(3, i, j);
			}
		}
	}
	dfs(camera[0].dir, camera[0].x, camera[0].y, 0);
	cout << result << '\n';
}

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

문제

문제

출처

ICPC

[C]질문글들의 모든 반례가 다 맞습니다...ㅠ

qmdlrbwls 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말