글 읽기 - 2638번 반례가 있을까요.

peter4549 3년 전 0

일단 1번 dfs로 외부공기를 전부 2로 만들고,

남은 치즈 체크하면서 2차 루프로 치즈(1)인 경우 인접 외부 공기 체크해서 (2면 이상 외부공기랑 접촉하는 경우) 0으로 만듭니다.

그리고 한번 더 2차 루프 돌리면서 0인 경우 인접 외부공기가 하나라도 있는 경우 2로 만듭니다.

치즈가 1->0이라는 것은 인접하는 외부공기가 반드시 있다는 말이고, 치즈가 녹은 지점을 타고 외부공기가 내부로 들어갈 수 있을 텐데..

일단 예제랑 반례들로 테스트 해봤을 때는 잘 맞게 나오는데 제출하면 바로 틀리더라구요..

어디가 문제인지 한번 확인해주시면 감사하겠습니다.

#include <cstdio>

const int dy[4] = { -1, 0, 1, 0 };
const int dx[4] = { 0, -1, 0, 1 };

int N, M;
int grid[101][101];

void dfs(int y, int x) {
	grid[y][x] = 2;

	for (int d(0); d < 4; ++d) {
		int ny(y + dy[d]);
		int nx(x + dx[d]);

		if (0 > ny || ny >= N || 0 > nx || nx >= M)
			continue;

		if (!grid[ny][nx])
		    dfs(ny, nx);
	}
}

bool cheese_exist() {
	for (int i(0); i < N; ++i)
		for (int j(0); j < M; ++j)
			if (grid[i][j] == 1)
				return true;

	return false;
}

void melt(int y, int x) {
	int count(0);

	for (int d(0); d < 4; ++d) {
		int ny(y + dy[d]);
		int nx(x + dx[d]);

		if (0 > ny || ny >= N || 0 > nx || nx >= M)
			continue;

		if (grid[ny][nx] == 2)
			++count;

		if (count >= 2) {
			grid[y][x] = 0;
			return;
		}
	}
}

void air_expose(int y, int x) {
	for (int d(0); d < 4; ++d) {
		int ny(y + dy[d]);
		int nx(x + dx[d]);

		if (0 > ny || ny >= N || 0 > nx || nx >= M)
			continue;

		if (grid[ny][nx] == 2) {
			grid[y][x] = 2;
			return;
		}
	}
}

int main() {
	int hours(0);

	scanf("%d %d", &N, &M);

	for (int i(0); i < N; ++i)
		for (int j(0); j < M; ++j)
			scanf("%d", &grid[i][j]);

	dfs(0, 0);
	
	while (cheese_exist()) {
		++hours;

		for (int i(1); i < N - 1; ++i) {
			for (int j(1); j < M - 1; ++j) {
				if (grid[i][j] == 1) {
					melt(i, j);
				}
			}
		}
	
		for (int i(1); i < N - 1; ++i) {
			for (int j(1); j < M - 1; ++j) {
				if (grid[i][j] == 0) {
					air_expose(i, j);
				}
			}
		}
	}

	printf("%d", hours);

	return 0;
}

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

문제

문제

출처

ICPC

2638번 반례가 있을까요.

peter4549 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말