글 읽기 - 반례가 뭘까요

apdh25 4년 전 0

질문게시판에 있는 반례찾아서 고쳐보고했는데 흠... 어느조건을 빼먹은걸까요?..

일단 보드에 있는 모든 뿌요뿌요들을 각각을 BFS로 탐색해서 4개이상인 부분들 지워주고 연쇄개수 1증가시키고

그다음에 싹다 내려주고 다시 BFS로 해주고 종료조건은 4개 이상인 BFS가 더이상 안지워질때 로 햇는데..

한번만 봐주시고 피드백주시면 감사드리겟습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> Pair;

const int dx[] = { 0,0,1,-1 }; //동서남북
const int dy[] = { 1,-1,0,0 };

vector<vector<char>>board;
vector<vector<bool>>visited;

int cnt = 0;
int n = 12, m = 6;

void erase_puyo()
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (visited[i][j]) {
				board[i][j] = '.';
			}
		}
	}

}

int bfs(char color, Pair start)
{
	queue<Pair> q;
	int step = 1;

	q.push(start);
	visited[start.first][start.second] = true;

	while (q.empty() != true)
	{
		Pair pos = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) 
		{
			Pair next = Pair(pos.first + dx[i], pos.second + dy[i]);

			if (next.first > n || next.first<1 || next.second>m || next.second < 1)
				continue;

			if (!visited[next.first][next.second] && board[next.first][next.second] == color) {
				visited[next.first][next.second] = true;
				step++;
				q.push(next);
			}
		}
	}
	return step;
}

int puyo_bfs(int turn)
{
	int ret = 0;
	visited = vector<vector<bool>>(n + 1, vector<bool>(m + 1));

	if (turn == 1) {
		//Red
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (visited[i][j] != true && board[i][j] == 'R') {
					if (bfs('R', Pair(i, j)) >= 4)
					{
						erase_puyo();
						ret = 1;
					}
				}
			}
		}
	}
	else if (turn == 2) {
		//Green
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (visited[i][j] != true && board[i][j] == 'G') {
					if (bfs('G', Pair(i, j)) >= 4)
					{
						erase_puyo();
						ret = 1;
					}
				}
			}
		}
	}
	else if (turn == 3) {
		//Blue
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (visited[i][j] != true && board[i][j] == 'B') {
					if (bfs('B', Pair(i, j)) >= 4)
					{
						erase_puyo();
						ret = 1;
					}
				}
			}
		}
	}
	else if (turn == 4) {
		//Purple
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (visited[i][j] != true && board[i][j] == 'P') {
					if (bfs('P', Pair(i, j)) >= 4)
					{
						erase_puyo();
						ret = 1;
					}
				}
			}
		}
	}
	else {
		//Yellow
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (visited[i][j] != true && board[i][j] == 'Y') {
					if (bfs('Y', Pair(i, j)) >= 4)
					{
						erase_puyo();
						ret = 1;
					}
				}
			}
		}
	}
	return ret;
}

void move(Pair pos, char color)
{
	int idx1 = pos.first;
	int idx2 = pos.second;

	while (board[idx1 + 1][idx2] == '.')
	{
		board[idx1 + 1][idx2] = color;
		board[idx1][idx2] = '.';
		idx1 = idx1 + 1;
	}
}

void puyo_down()
{
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= m; j++) {
			if (board[i][j] != '.') move(Pair(i, j), board[i][j]);
		}
	}
}

void solve()
{
	while (true)
	{
		int ret = 0;

		for (int i = 1; i <= 5; i++)
		{
			ret += puyo_bfs(i);
		}

		if (ret != 0) {
			puyo_down();
			cnt++;
		}
		else {
			break;
		}
	}
}

int main()
{
	board = vector<vector<char>>(20, vector<char>(20));

	for (int i = 1; i <= 12; i++) {
		for (int j = 1; j <= 6; j++) {
			cin >> board[i][j];
		}
	}

	solve();
	cout << cnt << endl;
	return 0;
}

clrmt 4년 전 2

우연히 이거 대입해봤는데 1나오네요.

답은 2입니다.

......
......
......
......
......
....Y.
....Y.
....Y.
....RR
...YRR
..GGYY
..GGYY

apdh25 4년 전 0

덕분에 해결했습니다ㅠㅠ BFS를 돌때마다 4개이상모여있는 군집들만 지워야하는 코드, 밑으로 내려가는 move 함수코드를 잘못짰네요ㅎㅎ.. 감사드립니다!

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

문제

문제

출처

ICPC

반례가 뭘까요

apdh25 4년 전 0

clrmt 4년 전 2

apdh25 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말