글 읽기 - 다른분들이 올려주신 반례도 다통과하는데 어디가 문제일까요

alsgud3229 5년 전 0

단지번호찾기와 같이 미네랄에 번호를 부여하여 다른번호끼리는 다른 클러스터라고 인식합니다.

그리고 n번클러스터중 그 어느것도 바닥이나 다른 클러스터에 닿지 않는다면 중력처럼 내려가게 구현하였습니다.

#include <iostream>
#include <cstring>

using namespace std;

int n, m, k;
int visited[102][102];
char map[102][102];
int order[102];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int cluster_num = 0;


void DFS(int x, int y, int num) {
	visited[x][y] = num;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m && visited[nx][ny]==0 && map[nx][ny]=='x') {
			DFS(nx, ny, num);
		}
	}
}

int findCluster() {
	int num = 0;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			if (visited[i][j]==0 && map[i][j] == 'x') {
				num++;
				DFS(i, j, num);
			}
		}
	}
	return num;
}

void printAll() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
}

void gravity(int num) {
	while (1) {
		bool flag = true;
		for (int i = n - 1; i >= 0; i--) {
			for (int j = m - 1; j >= 0; j--) {
				if (visited[i][j] != num) {
					continue;
				}
				else {
					if (i + 1 == n || (visited[i + 1][j] != num && visited[i + 1][j] > 0)) {
						// 이미 바닥이거나 다른 클러스터 만날예정이면
						flag = false;
					}
				}
			}
		}
		if (!flag) {
			break;
		}
		else{
			for (int i = n - 1; i >= 0; i--) {
				for (int j = m - 1; j >= 0; j--) {
					if (visited[i][j] != num) {
						continue;
					}
					else {
						map[i + 1][j] = map[i][j];
						map[i][j] = '.';
						visited[i + 1][j] = visited[i][j];
						visited[i][j] = 0;
					}
				}
			}
		}
		
	}
}

void find_floating() {
	// floating 인 클러스터를 찾고 중력처리해줌
	for (int num = 1; num <= cluster_num; num++) {
		bool flag = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (visited[i][j] != num) {
					continue;
				}
				else {
					if (i == n - 1) {
						flag = true;
					}
				}
			}
		}
		if (!flag) { // 클러스터의 요소중 바닥에 닿는애가 하나도 없는것
			// num의 cluster가 공중에 떠있음
			//cout << "cluster number:" << num << " is floating\n";
			gravity(num);
		}
	}
}

void crash(int h, int pattern) {
	if (pattern % 2 == 0) {
		// -->
		for (int j = 0; j < m; j++) {
			if (map[h][j] == 'x') {
				map[h][j] = '.';
				return;
			}
		}

	}
	else {
		// <--
		for (int j = m - 1; j >= 0; j--) {
			if (map[h][j] == 'x') {
				map[h][j] = '.';
				return;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	cin >> k;
	for (int i = 0; i < k; i++) {
		int kk;
		cin >> kk;
		order[i] = n - kk; 
	}

	for (int i = 0; i < k; i++) {
		crash(order[i], i);
		cluster_num = findCluster();
		find_floating(); 	// floating 인 클러스터를 찾고 중력처리해줌
		memset(visited, 0, sizeof(visited));
	}

	printAll();

	return 0;
}

wjdclgns12 5년 전 1

출력할때 글자 사이사이에 빈칸을 출력하면 안됩니다.

alsgud3229 5년 전 0

허무하네요 ㅠㅠ 덕분에 정답입니다 감사합니다

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

문제

문제

출처

ICPC

다른분들이 올려주신 반례도 다통과하는데 어디가 문제일까요

alsgud3229 5년 전 0

wjdclgns12 5년 전 1

alsgud3229 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말