글 읽기 - 어떤 반례가 존재하나요?(수정)

sds4631 5년 전 1

문제의 예시와 질문게시판에 올라온 반례들을 모두 만족시키는데 틀렸다고 출력이 됩니다.

개인적으로 여러 반례를 만들어봤는데 찾지못하였습니다.

혹시 어떤 반례가 존재하는지 알 수 있을까요?

#define _CRT_SECURE_NO_WARNINGS

#include <string>
#include <vector>
#include <iostream>
#include <string.h>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int chain = 0;


char map[12][6];
bool check[12][6] = { false , };
bool con2 = false;

bool clear() {
	int c = 0,i,k,j;
	bool con = false;
	for ( i = 0; i < 6; i++) {
		for ( k = 11; k >= 0; k--) {
			if (map[k][i] == '.') {
				for ( j = k; j >= 0; j--) {
					if (map[j][i] != '.') {
						map[j + c][i] = map[j][i];
						map[j][i] = '.';
						con = true;
					}
					else {
						c++;
					}
				}
				c = 0;
				break;
			}
		}
	}
	if (con) {
		return true;
	}
	return con;
}
void bang(queue<pair<int, int>> dlt) {
	int c = 0;
	pair<int, int> loca_1;
	con2 = true;
	while (!dlt.empty()) {
		loca_1 = dlt.front();
		dlt.pop();
		map[loca_1.first][loca_1.second] = '.';
	}

}
bool bfs(queue<pair<int, int>> py) {
	pair <int, int> location1;
	queue<pair<int, int>> dlt, nep;
	bool con = false;
	location1 = py.front();
	while (!py.empty()) {
		location1 = py.front();
		py.pop();
		nep.push(location1);
		while (!nep.empty()) {
			location1=nep.front();
			nep.pop();
			if (check[location1.first][location1.second] == true) {
				continue;
			}
			else {
				check[location1.first][location1.second] = true;
				dlt.push(location1);
				if (location1.first - 1 >= 0) {
					if (map[location1.first][location1.second] == map[location1.first - 1][location1.second]) {
						location1.first--;
						nep.push(location1);
						location1.first++;
					}
				}
				if (location1.first + 1 < 12) {
					if (map[location1.first][location1.second] == map[location1.first + 1][location1.second]) {
						location1.first++;
						nep.push(location1);
						location1.first--;
					}
				}
				if (location1.second - 1 >= 0) {
					if (map[location1.first][location1.second] == map[location1.first][location1.second - 1]) {
						location1.second--;
						nep.push(location1);
						location1.second++;
					}
				}
				if (location1.second + 1 < 12) {
					if (map[location1.first][location1.second] == map[location1.first][location1.second + 1]) {
						location1.second++;
						nep.push(location1);
						location1.second--;
					}
				}
			}
		}
		if (dlt.size() >= 4) {
			bang(dlt);
			return true;
		}
		else {
			return false;
		}
	}
}

int main() {
	queue <pair<int, int>> R,G,B,Y,P;
	pair <int, int> location;
	queue<pair<int, int>> dlt;
	bool con = false;
	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {
			cin >> map[i][j];
		}
	}
	while (1) {
		for (int i = 12; i >=0; i--) {
			for (int j = 5; j >=0; j--) {
				if (map[i][j] == 'R') {
					location.first = i;
					location.second = j;
					R.push(location);
				}
				else if (map[i][j] == 'Y') {
					location.first = i;
					location.second = j;
					Y.push(location);
				}
				else if (map[i][j] == 'G') {
					location.first = i;
					location.second = j;
					G.push(location);
				}
				else if (map[i][j] == 'B') {
					location.first = i;
					location.second = j;
					B.push(location);
				}
				else if (map[i][j] == 'P') {
					location.first = i;
					location.second = j;
					P.push(location);
				}
			}
		}
		do {
			con = false;
			if (!R.empty()) {
				dlt.push(R.front());
				con = bfs(R);
				memset(check,false,sizeof(check));
				queue<pair<int, int>> ept;
				R.swap(ept);
			}
			if (!Y.empty()) {
				dlt.push(Y.front());
				con = bfs(Y);
				memset(check, false, sizeof(check));
				queue<pair<int, int>> ept;
				Y.swap(ept);

			}
			if (!G.empty()) {
				dlt.push(G.front());

				con = bfs(G);
				memset(check, false, sizeof(check));
				queue<pair<int, int>> ept;
				G.swap(ept);
			}
			if (!B.empty()) {
				dlt.push(B.front());
				con = bfs(B);
				memset(check, false, sizeof(check));
				queue<pair<int, int>> ept;
				B.swap(ept);
			}
			if (!P.empty()) {
				dlt.push(P.front());
				con = bfs(P);
				memset(check, false, sizeof(check));
				queue<pair<int, int>> ept;
				P.swap(ept);
			}
		} while (con);
		if (con2) {
			chain++;
			con2 = false;
		}
		if (clear()){
			continue;
		}
		else {
			break;
		}
	}
	cout << chain<<endl;
}

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

문제

문제

출처

ICPC

어떤 반례가 존재하나요?(수정)

sds4631 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말