글 읽기 - 어느부분이 틀린건지 모르겠습니다(반례다맞음)

wjavm2 4년 전 1

11%에서 틀렸습니다가 나오는데 어느부분에서 틀린건지 모르겠습니다....

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

struct Dist { int x, y; 
bool operator < (const Dist& A)
{
	return x>A.x;
};
};
int R, C, N;
char Map[150][150];
int Cpy[150][150];
int Order[110];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void Is_Seperate(int x, int y);
void DFS(int x, int y, int cnt);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> R >> C;

	for (int a = 1; a <= R; a++)
	{
		for (int b = 1; b <= C; b++)
		{
			cin >> Map[a][b];
		}
	}

	
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> Order[i];
	}

	for (int i = 1; i <= N; i++)
	{
		int col = R - Order[i] + 1;
		int row = 0;
		bool erase = false;

		if (i % 2 != 0)//홀수 ->
		{
			for (int j = 1; j <= C; j++)
			{
				if (Map[col][j] == 'x')
				{
					if (erase) {
						row = j;
						break;
					}
					else if(!erase)
					{
						Map[col][j] = '.';
						erase = true;
					}
				}	
			}
		}
		else if(i% 2 == 0) //짝수 <-
		{
			for (int j = C; j >= 1; j--)
			{
				if (Map[col][j] == 'x')
				{
					if (erase) {
						row = j;
						break;
					}
					else if (!erase)
					{
						Map[col][j] = '.';
						erase = true;
					}

				}
			}
		}
		//클러스터가 분리되었는지 확인하고 아래로 내려갈 수 있으면 내리는 함수
		Is_Seperate(col, row);
		
	}
    
    for (int i = 1; i <= R; i++)
		{
			for (int j = 1; j <= C; j++)
			{
				cout << Map[i][j];
			}
			cout << endl;
		}
	
	
	return 0;
}

void Is_Seperate(int x, int y)
{
	memset(Cpy, 0, sizeof(Cpy));
	bool down[110] = { false };

	int cnt = 0;
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			if (Map[i][j] == 'x' && Cpy[i][j] == 0) //DFS로 클러스트 몇개인지 구분
			{
				cnt++;
				Cpy[i][j] = cnt;
				DFS(i, j, cnt);
			}
		}
	}

	if (cnt > 1)//클러스터가 1개이상일경우 중력작용 처리해줘야하는 클러스터 생길수 있음
	{
		for (int h = 1; h <= C; h++)
		{
			if (Cpy[R][h] > 0)
			{
				down[Cpy[R][h]] = true; //바닥에 몇번째 클러스터가 붙어있는지확인
			}
		}

		int down_num = 0;
		for (int i = 1; i <= cnt; i++)
		{
			if (down[i] == false)
			{
				down_num = i; //바닥에 붙어있지 않은 클러스터 중력법칙적용해야하
				break;
			}
		}
		
		vector<Dist>D;

		if (down_num > 0) //클러스터 번호가 0보다 클경우(중력법칙해줘야함)
		{
			for (int i = 1; i <= R; i++)
			{
				for (int j = 1; j <= C; j++)
				{
					if (Cpy[i][j] == down_num)
					{
						Map[i][j] = '.';
						D.push_back({ i,j }); //해당 클러스터 모두 벡터에넣고 맵 초기화
					}
				}
			}
			sort(D.begin(), D.end()); //x값이 큰순서대로 정렬(제일 바닥의 클러스터 x값구하기위해)

			int mmax_col = 0;

			for (int k = R - D[0].x; k >= 1; k--) { 

				bool cant = false;
				mmax_col = k;
				for (int i = 0; i < D.size(); i++)
				{
					int nx = D[i].x + k;
					int ny = D[i].y;
					if (Map[nx][ny] == 'x')
					{
						cant = true;
						break;
					}
				}
				if (!cant)break; //만약 클러스터의 모든 부분이 중력법칙작용가능하면
			}
		
			for (int i = 0; i < D.size(); i++)
			{
				int nx = D[i].x + mmax_col; //중력법칙적용
				int ny = D[i].y;
			
				Map[nx][ny] = 'x';
			}		
		}
	}
}

void DFS(int x, int y, int cnt) //클러스터 영역구하기
{
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx<1 || ny<1 || nx>R || ny>C)continue;
		if (Map[nx][ny] == 'x' && Cpy[nx][ny] == 0) {
			Cpy[nx][ny] = cnt;
			DFS(nx, ny, cnt);
		}
	}
}

wjavm2 3년 전 0

아래와 같이 다시 설계해서 풀었더니 맞았습니다!

다시 설계할때, 중력법칙적용해야하는 클러스터가 아래로 내려갈 수 있는 최솟값을 구하고 하나씩 더해주면서 내려갈때 Map의 범위를 넘어가는 부분을 리턴시켜주었더니 맞았습니당

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

using namespace std;

struct info { int x, y; };
int R, C, N;
int Throw[110];
char Map[110][110];
bool check[110][110];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<info>IDX;



int Left(int floor);
int Right(int floor);
void Down();
bool Can_down();
void gravity();
void DFS(int x, int y);

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> R >> C;
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			cin >> Map[i][j];
		}
	}
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> Throw[i];
	}

	for (int i = 1; i <= N; i++)
	{
		int x = -1;

		if (i % 2 != 0)
		{
			x = Left(R-Throw[i]+1);
		}
		else
		{
			x = Right(R-Throw[i]+1);
		}
		/*cout << "Clear\n";
		for (int i = 1; i <= R; i++)
		{
			for (int j = 1; j <= C; j++)
			{
				cout << Map[i][j];
			}
			cout << "\n";
		}
		cout << "\n";*/
		if (x > -1) 
		{

			Down();
		}
		/*
		cout << "Down\n";
		for (int i = 1; i <= R; i++)
		{
			for (int j = 1; j <= C; j++)
			{
				cout << Map[i][j];
			}
			cout << "\n";
		}
		cout << "\n";*/
	}

	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			cout << Map[i][j];
		}
		cout << "\n";
	}

	return 0;
}


int Left(int floor)
{
	int j = -1;
	//cout <<"L"<< floor << "\n";
	for (int i = 1; i <= C; i++)
	{
		if (Map[floor][i] == 'x')
		{
			j = i;
			Map[floor][i] = '.';
			break;
		}
	}

	return j;
}

int Right(int floor)
{
	int j = -1;
	//cout << "R"<< floor << "\n";
	for (int i = C; i >= 1; i--)
	{
		if (Map[floor][i] == 'x')
		{
			Map[floor][i] = '.';
			j = i;
			break;
		}
	}
	return j;
}

void Down()
{
	if (Can_down())
	{
		//cout << "cc" << "\n";
		gravity();
	}
	return;
}

bool Can_down()
{
	memset(check, false, sizeof(check));

	for (int i = 1; i <= C; i++)
	{
		if (Map[R][i] == 'x' && !check[R][i])
		{
			check[R][i] = true;
			DFS(R, i);
		}
	}

	IDX.clear();
	bool flag = false;

	for (int i = R; i >= 1; i--)
	{
		for (int j = 1; j <= C; j++)
		{
			if (Map[i][j] == 'x' && !check[i][j])
			{
				Map[i][j] = '.';
				flag = true;
				IDX.push_back({ i,j });
			}
		}
	}

	return flag;
}


void gravity()
{
	int Min = 987654321;

	for (int i = 0; i < IDX.size(); i++)
	{
		int cx = IDX[i].x;
		int cy = IDX[i].y;
		
		int cnt = 0;
		while (Map[cx+1][cy] == '.' && cx <= R)
		{
			cnt++;
			cx += 1;
		}
		Min = min(Min, cnt);
	}
	
	for (int i = 0; i < IDX.size(); i++)
	{
		if (IDX[i].x + Min > R)return;	//다음위치가 범위를 넘어갈경우 리턴
	}

	for (int i = 0; i < IDX.size(); i++)
	{
		
		int cx = IDX[i].x;
		int cy = IDX[i].y;
		
		Map[cx + Min][cy] = 'x';
		/*
		cout << "\n";
		for (int i = 1; i <= R; i++)
		{
			for (int j = 1; j <= C; j++)
			{
				cout << Map[i][j];
			}
			cout << "\n";
		}*/ 
	}

}

void DFS(int x, int y)
{
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx<1 || ny<1 || nx>R || ny>C)continue;
		if (Map[nx][ny] == 'x' && !check[nx][ny])
		{
			check[nx][ny] = true;
			DFS(nx, ny);
		}
	}
}

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

문제

문제

출처

ICPC

어느부분이 틀린건지 모르겠습니다(반례다맞음)

wjavm2 4년 전 1

wjavm2 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말