글 읽기 - 30%에서 자꾸 틀립니다..

khg8016 7년 전 0

BFS 방식으로 큐에 각 구슬의 좌표를 담는 방식으로 풀었구요. 설명은 주석 달아놓았습니다..

30%에서 자꾸 틀리는데 어디서 틀린지 모르겠습니다 ㅠㅠ

#include <queue>
#include <iostream>
using namespace std;
int main() {
	int n, m, ans = 0;
	int dx[4] = { -1,0,1,0 };
	int dy[4] = { 0,1,0,-1 }; 
	char map[11][11];
	bool checkRED[11][11], checkBLUE[11][11];
	int dest_x, dest_y; //목표 위치
	queue<pair<int, int> > q, q2; //빨간 구슬, 파란 구슬 위치 담을 queue
	cin >> n >> m;
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1;j < m + 1; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'R') q.push(make_pair(i, j));
			if (map[i][j] == 'B') q2.push(make_pair(i, j));
			if (map[i][j] == 'O') { dest_x = i; dest_y = j; }
			checkRED[i][j] = checkBLUE[i][j] = false;
		}
	}
	while (!q.empty()) {
		ans++;
		int size = q.size();
		while (size--) {
			int r_x = q.front().first, r_y = q.front().second;//현재 빨간 구슬 위치
			int b_x = q2.front().first, b_y = q2.front().second; //현재 파란구슬 위치
			checkRED[r_x][r_y] = checkBLUE[b_x][b_y] = true;
			q.pop();q2.pop();
			for (int i = 0; i < 4; i++) {
				int rx2 = r_x, ry2 = r_y, bx2 = b_x, by2 = b_y;
				bool rflag = false, bflag = false, ansflag = false, ansflag2 = false;
				while (!rflag || !bflag) {
					int n_rx = rx2 + dx[i], n_ry = ry2 + dy[i];
					int n_bx = bx2 + dx[i], n_by = by2 + dy[i];
					if (n_rx <= n && n_rx >=1 && n_ry <= m && n_ry>=1 && !rflag) {						
						if (map[n_rx][n_ry] == '#') rflag = true; //다음 방향이 #이면 빨간 구슬 멈춤
						else if (map[n_rx][n_ry] == 'O') {//다음 방향이 O이면 빨간구슬 멈춤
							ansflag = true;
							rflag = true;
						}
						else { rx2 = n_rx; ry2 = n_ry; }//둘다 아니면 계속 진행
					}
					if (n_bx <= n && n_bx >=1 && n_by <= m && n_by>=1 && !bflag) {//파란구슬도 위와 같은방식					
						if (map[n_bx][n_by] == '#') bflag = true;
						else if (map[n_bx][n_by] == 'O') {
							ansflag2 = true;
							bflag = true;
						}
						else { bx2 = n_bx; by2 = n_by; }						
					}					
				}
				if (ansflag2) continue;//파란 구슬이 빠졌으면 continue
				if (ansflag) { //파란구슬 안빠지고 빨간구슬 빠지면 정답
					cout << ans << endl;
					return 0;					
				}
                //두 구슬 모두 안빠지면
				if (rx2 == bx2 && ry2 == by2) { //이동 하고나서 구슬위치가 똑같을 때(부딪혔을 때)
					if (r_x == b_x) {//기존 위치가 같은 행에 위치했을 때 
						if (r_y > b_y) {// B R 순서일때 
							if (i == 1) by2--; //오른쪽 진행 방향이였으면 파란 구슬 한칸 왼쪽
							if (i == 3) ry2++; //왼쪽 진행 방향이였으면 빨간 구슬 한칸 오른쪽
						}
						else { //R B 순서 일 때
							if (i == 1) ry2--;
							if (i == 3) by2++;
						}
					}
					if (r_y == b_y) { //기존 위치가 같은 열에 위치
						if (r_x > b_x) {//빨간 구슬이 원래 더 아래 있을 때
							if (i == 2) bx2--; //아래쪽 진행방향 이였을때 파란 구슬 한칸 위로
							if (i == 0) rx2++;//위쪽 진행방향 이였을 때 빨간구슬 한칸 아래로
						}
						else {
							if (i == 2) rx2--;
							if (i == 0) bx2++;
						}
					}
				}
				if (!checkRED[rx2][ry2] || !checkBLUE[bx2][by2]) {//둘중 하나라도 check안되어있으면
					q.push(make_pair(rx2, ry2)); //이동 
					q2.push(make_pair(bx2, by2));
					checkRED[rx2][ry2] = checkBLUE[bx2][by2] = true;
				}
			}
		}
		if (ans == 10) break;
	}
	cout << -1 << endl; //10번 이내로 못찾으면 -1 출력
	return 0;
}

khg8016 7년 전 0

checkRED[rx2][ry2], checkBLUE[bx2][by2] 이렇게 나눠서 했다가 (하나라도 false이면 다음 단계로 이동)

chk[11][11][11][11] 합쳐서 하나의 배열로 했더니 해결되네요.

나눠서 하면 왜 안되는건지 모르겠네요..

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

문제

문제

출처

ICPC

30%에서 자꾸 틀립니다..

khg8016 7년 전 0

khg8016 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말