글 읽기 - 어디서 틀린지 도저히 못찾겠습니다..

jun071994 4년 전 0

게시판과 인터넷에 있는 예제는 모두 맞는데 채점하자마자 틀렸습니다가 나옵니다..

제가 한 방식은 막대기에 의해서 미네랄이 부서지면

부서진 미네랄을 기준으로 4방향에 대해서 BFS로 탐색해서 클러스터를 형성하고

클러스터를 1칸씩 내리면서 떨어뜨릴수 있는지 없는지 확인합니다.

도와주시면 감사하겠습니다..

/*
백준 2933: 미네랄

깨진 얼음을 기준으로 상하좌우 BFS로 탐색한다.
-> 각 방향을 탐색중에 바닥에 있는 미네랄이 있다면 다음 방향으로
->
*/
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int R, C, N;
int board[100][100];
int tmp_board[100][100];
bool vis[100][100];
int height[100];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<pair<int, int>> cluster;
void Input() {
	cin >> R >> C;
	
	for (int i = R - 1; i >= 0; i--) {
		string input;
		cin >> input;
		for (int j = 0; j < C; j++) {
			if (input[j] == '.')
				board[i][j] = 0;
			else if (input[j] == 'x')
				board[i][j] = 1;
		}
	}
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> height[i];
	}
	/*cout << "-----------" << endl;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cout << board[i][j];
		}
		cout << endl;
	}
	cout << "-----------" << endl;*/
}
bool IsRange(int x, int y){
	return x >= 0 && x < R && y >= 0 && y < C;
}
bool cmp(pair<int, int> A, pair<int, int> B) {
	return A.first < B.first;
}
void Print() {
	for (int i = R - 1; i >= 0; i--) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 0) {
				cout << '.'; 
		}
			else if (board[i][j] == 1) {
				cout << 'x'; 
			}
		}
		cout << endl;
	}

}
void BFS(int x, int y) {
	//cout << x << " " << y << endl;
	memset(vis, 0, sizeof(vis));
	vis[x][y] = true;
	board[x][y] = 0;
	//Print();
	for (int i = 0; i < 4; i++) {
		if (board[x + dx[i]][y + dy[i]] == 0 || vis[x + dx[i]][y + dy[i]])
			continue;
		queue<pair<int, int>> que;
		cluster.clear();
		que.push(make_pair(x + dx[i], y + dy[i]));
		cluster.push_back(make_pair(x + dx[i], y + dy[i]));
		vis[x + dx[i]][y + dy[i]] = true;
		bool flag = true;
		while (!que.empty()) {
			auto cur = que.front();
			que.pop();
			for (int j = 0; j < 4; j++) {
				int nx = cur.first + dx[j];
				int ny = cur.second + dy[j];
				
				if (!IsRange(nx, ny) || board[nx][ny] == 0 || vis[nx][ny]) {
					//cout << "fuck: " << nx << " " << ny<<" "<<IsRange(nx,ny)<<" "<<board[nx][ny]<<" " <<vis[nx][ny]<< endl;
					continue;
				}
				if (nx == 0) {
					flag = false;
					break;
				}
				que.push(make_pair(nx, ny));
				cluster.push_back(make_pair(nx, ny));
				vis[nx][ny] = true;
			}
		}
		if (!flag)
			continue;
		//떨어뜨리기
		sort(cluster.begin(), cluster.end(), cmp);
		/*cout << "깨진 미네랄: " << x << " " << y << endl;
		for (int j = 0; j < cluster.size(); j++) {
			cout<<"클러스터: " << cluster[j].first << " " << cluster[j].second << endl;
		}*/
		
		for (int j = 0; j < R; j++) { //맵 복사
			for (int k = 0; k < C; k++) {
				tmp_board[j][k] = board[j][k];
			}
		}
		for (int j = 1; j <= x; j++) {
			bool flag = true;
			for (int k = 0; k < cluster.size(); k++) {
				int nx = cluster[k].first;
				int ny = cluster[k].second;
				if (tmp_board[nx - 1][ny] == 1 || nx == 0) { //다른 클러스터를 만나거나 바닥인경우?
					flag = false;
					break;
				}
				else {
					tmp_board[nx - 1][ny] = 1;
					tmp_board[nx][ny] = 0;
				}
			}
			if (!flag) { //복원해야함.
				break;
			}
			else { //클러스터 1칸 떨어뜨렸으니 좌표 1개씩 바궈야함
				//cout << "hi" << endl;
				for (int k = 0; k < cluster.size(); k++) {
					cluster[k].first--;
				}

				for (int k = 0; k < R; k++) { //맵 적용
					for (int l = 0; l < C; l++) {
						board[k][l] = tmp_board[k][l];
					}
				}
			}


		}

		break;
	}

}

void Solution() {
	for (int i = 0; i < N; i++) {
		//i가 0,2 .. 짝수면 왼쪽부터
		//i가 1,3... 홀수면 오른쪽부터
		if (i % 2 == 0) {
			for (int j = 0; j < C; j++) {
				if (board[height[i]-1][j] == 1) {
					BFS(height[i]-1,j);
					break;
				}
			}
		}
		else {
			for (int j = C - 1; j >= 0; j--) {
				if (board[height[i]-1][j] == 1) {
					BFS(height[i] - 1,j);
					break;
				}
			}
		}
		//Print();
	}

}

void Solve() {
	Input();
	Solution();
	Print();
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	Solve();
	return 0;
}

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

문제

문제

출처

ICPC

어디서 틀린지 도저히 못찾겠습니다..

jun071994 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말