글 읽기 - (C++)9%에서 틀렸다고 나옵니다.

ahdtld54 2년 전 0

반례들을 다 넣어봤을 때 답이 잘 나오는데 반례를 알려주실 수 있나요..?

#include <iostream>
#include <vector>

using namespace std;

int MAP[100][100], N, M;
int n_y[4] = { 0, 1, 0, -1 }, n_x[4] = { 1,0,-1,0 };

void dfs_air(int y, int x) {
	if (MAP[y][x] != 0)
		return;
	else {
		MAP[y][x] = -1;
		int next_y, next_x;
		for (int i = 0; i < 4; i++) {
			next_y = y + n_y[i], next_x = x + n_x[i];
			if ((next_y >= 0 && next_y < N) && next_x >= 0 && next_x < M) {
				dfs_air(next_y, next_x);
			}
		}
	}
}

void air() {
	for(int i=0; i<N; i++)
		for (int j = 0; j < M; j++) 
			if (!MAP[i][j]) {
				dfs_air(i, j);
				return;
			}
}

int main(void) {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> MAP[i][j];
	int clear = 0;
	int answer = 0;
	while (1) {
		vector<pair<int, int>> vt;
		air();
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (MAP[i][j] == 1) {
					int cnt = 0;
					for (int k = 0; k < 4; k++) {
						int y = i + n_y[k], x = j + n_x[k];
						if ((y >= 0 && y < N) && (x >= 0 && x < M)) {
							if (MAP[y][x] == -1)
								cnt++;
						}
					}
					if (cnt >= 2) {
						vt.push_back(make_pair(i, j));
					}
				}
			}
		}
		if (vt.empty())
			break;
		for (int i = 0; i < vt.size(); i++) {
			MAP[vt[i].first][vt[i].second] = -1;
		}
		answer++;
	}
	cout << answer;
}

azberjibiou 2년 전 2

air()에서 가장 바깥에서 dfs를 시작해야 하는데 -1을 초기화하지 않아서 가장 바깥이 아닌 안쪽에서 dfs를 시작하는 경우가 있네요

7
0 0 0 0 0 0
1 1 0 1 1 0
1 1 1 1 1 0
0 1 0 1 0 0
1 1 1 1 1 0
1 1 0 1 1 0
0 0 0 0 0 0

출력: 2
정답: 3

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

문제

문제

출처

ICPC

(C++)9%에서 틀렸다고 나옵니다.

ahdtld54 2년 전 0

azberjibiou 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말