글 읽기 - c++) 11559번 dfs문제 틀렸습니다 반례가 뭘까요?

leewwo2o 5년 전 0

틀렸습니다가 나옵니다. 이 문제 다른 분 질문에 있는 반례들을 찾아서 다 해보았는데 다 맞습니다.

반례를 못찾겠습니다. 어떤 반례가 있을까요?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
char c[12][6];
int ck=0,ar[12][6];
void dfs(int i, int j,char cc) {
	if (i < 0 || i>11 || j < 0 || j>5) {
		return;
	}
	else if(c[i][j]==cc&&ar[i][j]==0){
		ar[i][j] = 1;
		ck++;
		dfs(i + 1, j, cc);
		dfs(i - 1, j, cc);
		dfs(i, j + 1, cc);
		dfs(i, j - 1, cc);
	}
}
void bomb() {
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			if (ar[i][j] == 1) {
				c[i][j] = '.';
				ar[i][j] = 0;
			}
		}
	}
}
void gravity() {
	for (int i = 11; i >= 0; i--) {
		for (int j = 5; j >= 0; j--) {
			if (c[i][j] == '.'&&c[i - 1][j] != '.') {
				c[i][j] = c[i - 1][j];
				c[i - 1][j] = '.';
				i = 11;
				j = 5;
			}
		}
	}
}
int main()
{
	int ans = 0,solve=0,check=0;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			cin >> c[i][j];
			ar[i][j] = 0;
		}
	}
	while (1) {
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				ck = 0;
				if (c[i][j] != '.') {
					dfs(i, j, c[i][j]);
					if (ck >= 4) {
						check++;
						bomb();
					}
				}
				for (int i = 0; i < 12; i++) {
					for (int j = 0; j < 6; j++)
						ar[i][j] = 0;
				}
			}
		}
		if (check > 0) {
			ans++;
			check = 0;
			gravity();
		}
		else
			break;
	}
	cout << ans;
	
	return 0;
}

djm03178 5년 전 1

터지자마자 바로 중력을 적용해서 하면 안 되고, 모든 뿌요를 터뜨린 뒤에 한 번에 떨어뜨려야 합니다.

......
......
......
......
......
......
......
Y.....
R.....
R.....
R.....
RYYY..

luniro 5년 전 0

32번째 줄 j의 범위는 왜 1~5인가요?

leewwo2o 5년 전 0

gravity()함수가 떨어뜨리는 함수인데 for문을 다 돌고 터트릴 수 있는거 다 터트리고 나서 한번 실행됩니다.

반례는 답이 2가 나옵니다.

그리고 32번째 줄을 >=0으로 범위를 바꿔도 틀렸다고 나오네요;;

djm03178 5년 전 0

제가 이 코드를 그대로 복붙해서 실행해봤는데 1이 출력됩니다.

어딘가 다른 곳에 문제점이 있겠군요.

https://ideone.com/xe4wLT

djm03178 5년 전 0

>=로 고치신 것까지 적용해야 2가 나오네요. 수정하신 뒤에는 코드도 업데이트를 해주세요.

leewwo2o 5년 전 0

아 네 수정했습니다. 수정하고 나서도 다른곳에 문제가 있네요.

djm03178 5년 전 0

그 뒤에 37번째 줄도 j = 6으로 바꾸면 통과됩니다. j=5로 했을 때의 반례는 위의 예시를 좌우로 뒤집기만 하면 됩니다.

j=5로 하게 되면 곧바로 루프에서 j--가 실행되면서 j=4가 되기 때문에 [11][5]에 대한 체크를 하지 못하기 때문입니다.

......
......
......
......
......
......
......
.....Y
.....R
.....R
.....R
..YYYR

leewwo2o 5년 전 0

아 답변 감사합니다 맞았습니다!!

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

문제

문제

출처

ICPC

c++) 11559번 dfs문제 틀렸습니다 반례가 뭘까요?

leewwo2o 5년 전 0

djm03178 5년 전 1

luniro 5년 전 0

leewwo2o 5년 전 0

djm03178 5년 전 0

djm03178 5년 전 0

leewwo2o 5년 전 0

djm03178 5년 전 0

leewwo2o 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말