글 읽기 - 2퍼에서 틀립니다. 왜 그런지 모르겠습니다. 게시판 반례 모두 통과합니다.

swrho 1년 전 0

2층부터 시작해서 한층씩 훝는 방식으로 진행하였습니다.

반례가 있을까요??

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <queue>

using namespace std;

int N, M, visit[55][55], Map[55][55], ans;
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
struct node {
	int x, y;
};
queue<node> Q;
int ifBoundary(int x, int y) {
	if (x == 0 || y == 0 || x == N - 1 || y == M - 1)
		return 1;
	return 0;
}
int inRange(int x, int y) {
	if (x < 0 || y < 0 || x >= N || y >= M) return 0;
	return 1;
}
void BFS(int x, int y, int h) { // h 층 검사
	int temp = 0, corrupt = 0;
	while (!Q.empty())	Q.pop();
	Q.push({ x,y });
	visit[x][y] = 1;
	while (!Q.empty()) {
		node cur = Q.front();
		Q.pop();
		temp++;
		node next;
		for (int d = 0; d < 4; d++) {
			next.x = cur.x + dx[d];
			next.y = cur.y + dy[d];
			if (inRange(next.x, next.y) == 0) continue;
			if (Map[next.x][next.y] >= h) continue;
			if (visit[next.x][next.y] == 1) continue;
			if (ifBoundary(next.x, next.y) == 1) {
				corrupt = 1;
				goto A;
			}
			visit[next.x][next.y] = 1;
			Q.push(next);
		}
	}
A:
	if (corrupt == 0) ans += temp;
	if (corrupt == 1) memset(visit, 0, sizeof(visit));
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			scanf("%1d", &Map[i][j]);

	for (int h = 2; h <= 9; h++) {
		memset(visit, 0, sizeof(visit));
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (Map[i][j] < h) {
					if (visit[i][j] == 0) {
						if(ifBoundary(i, j) == 0)
							BFS(i, j, h);
					}
				}
			}
		}
	}
	cout << ans;
}

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

문제

문제

출처

ICPC

2퍼에서 틀립니다. 왜 그런지 모르겠습니다. 게시판 반례 모두 통과합니다.

swrho 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말