글 읽기 - 반례를 알고 싶습니다.

jaeyoon8783 3년 전 0

미네랄 1은 통과한 사람입니다.

근데 이 문제에서는 50%에서 틀렸습니다. 라는게 나오는것을 봐선 그 반례에 막힌것 같습니다.

혹시 조언을 구할 수 있을까요???

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#define pii pair<int, int>
using namespace std;


char map[100][100];
int x, y;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };

void go(int sx, int sy, int check[][100], int cnt)
{
	check[sx][sy] = cnt;
	queue<pii> q;
	int max_x = sx;
	q.push({ sx,sy });

	while (!q.empty())
	{
		pii t = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];

			if (nx < 0 || nx >= x || ny < 0 || ny >= y)
				continue;


			if (map[nx][ny] == 'x' && check[nx][ny] == 0)
			{
				check[nx][ny] = cnt;
				q.push({ nx, ny });
				max_x = max(max_x, nx);
			}
		}
	}

	
	if (max_x == x - 1)//   해당 클러스터가 BFS로 탐색했을때 바닥에 닿은 미네랄이 있다면 이것은 붕 뜬것이 아니다.
		return;

	// 붕뜬거 가라앉히기


	int down = 101;
	for (int i = 0; i < y; i++)
	{
		int max_float_block = -1;
		
		for (int j = 0 ; j < x; j++)
		{
			if (map[j][i] == 'x' && check[j][i] == cnt)
				max_float_block = max(max_float_block, j);
		}

		if (max_float_block == -1)
			continue;


		int min_floor = x;

		for (int j = x - 1; j > max_float_block; j--)
		{
			if (map[j][i] == 'x' && check[j][i] != cnt)
				min_floor = min(min_floor, j);
		}
		down = min(down, min_floor - max_float_block);
	}

	for (int i = 0; i < y; i++)
	{
		for (int j = x-1; j >= 0; j--)
		{
			if (map[j][i] == 'x' && check[j][i] == cnt)
			{
				map[j][i] = '.';
				map[j + (down-1)][i] = 'x';
				check[j][i] = 0;
				check[j + (down - 1)][i] = cnt;
			}
		}
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> x >> y;

	for (int i = 0; i < x; i++)
	{
		for (int j = 0; j < y; j++)
			cin >> map[i][j];
	}


	int n, nn;
	cin >> n;

	for (int z = 0; z < n; z++)
	{
		cin >> nn;
		nn = x - nn; // nn은 x값

		int j;

		if (z % 2 == 0)
		{
			for (j = 0; j < y; j++)
			{
				if (map[nn][j] == 'x')
				{
					map[nn][j] = '.';
					break;
				}
			}
		}
		else
		{
			for (j = y - 1; j >= 0; j--)
			{
				if (map[nn][j] == 'x')
				{
					map[nn][j] = '.';
					break;
				}
			}
		}

		if (j == y || y == -1)
			continue;


		int cnt = 1;
		int check[100][100] = { 0 };
		for (int i = 0; i < x; i++)
		{
			for (int j = 0; j < y; j++)
			{
				if (map[i][j] == 'x' && check[i][j] == 0)
					go(i, j, check, cnt++);
			}
		}	
	}
	
	for (int i = 0; i < x; i++)
	{
		for (int j = 0; j < y; j++)
			cout << map[i][j];
		cout << '\n';
	}
	//cout << '\n';

}

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

문제

문제

출처

ICPC

반례를 알고 싶습니다.

jaeyoon8783 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말