글 읽기 - 22%에서 틀렸다고 나오는데 뭐가 문제일까요??

yth1130 5년 전 0

질문게시판에 있는 테스트케이스는 다 돌려봤습니다. 잘 돌아가구요

BFS를 이용해서 처음 R과 B구슬의 위치를 큐에 넣고

꺼내서 그 구슬을 보드위에 올려놓고 상하좌우로 움직여봐서 움직일 수 있으면

그 좌표를 큐에다 넣고 구슬을 보드에서 뺐습니다.

그리고 큐에서 꺼내면서 파란 구슬이 떨어졌거나 이동횟수가 10번을 넘었거나 이미 와본적이 있는 위치라면

움직여보지 않고 다음 좌표를 큐에서 꺼내는 방식으로 만들었습니다.

그리고 저만 잘 이해를 못했었나 싶었는데 만약

########

#O...RB#

######## 이런식으로 있으면 틀렸다고 나오는게 맞는 모양이더군요

저는 빨간게 먼저 들어가고 B는 보드위에 남는 방식인 줄 알고 그렇게 만들었다가 틀려서 그부분을 고쳐봤는데

여전히 같은 퍼센트에서 틀렸다고나옵니다... 머리에서 쥐날거같아요!!

뭐가 문제일까요... 알려주시면 감사하겠습니다!

#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
using namespace std;

string board[10];
queue<pair<pair<int, int>, int>> quR; //R구슬 좌표(y, x)와 상태(0이면 노말, 1이면 구멍에 빠짐).
queue<pair<pair<int, int>, int>> quB; //B구슬.
queue<int> quMov; //이동 횟수.

int dp[9][9][9][9]; //방문 여부, 0이면 방문 안함, 1이면 방문 함. ry rx by bx순.

void MoveUp(int& temp, int& isDrop, int Y, int X, char c);
void MoveDown(int& temp, int& isDrop, int Y, int X, char c);
void MoveLeft(int& temp, int& isDrop, int Y, int X, char c);
void MoveRight(int& temp, int& isDrop, int Y, int X, char c);

int main() {
	int N, M; //N:세로, M:가로.
	freopen("input.txt", "r", stdin);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> board[i];
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 'R') {
				quR.push({ { i,j }, 0 });
				quMov.push(0);
				board[i][j] = '.';
			}
			if (board[i][j] == 'B') {
				quB.push({ { i,j }, 0 });
				board[i][j] = '.';
			}
		}
	}
	bool success = false;
	int rX, rY, rS, movN, bX, bY, bS;
	while (!quR.empty()) {
		rY = quR.front().first.first;
		rX = quR.front().first.second;
		rS = quR.front().second;
		quR.pop();
		movN = quMov.front();
		quMov.pop();
		bY = quB.front().first.first;
		bX = quB.front().first.second;
		bS = quB.front().second;
		quB.pop();
		if (dp[rY][rX][bY][bX] == 1) continue; //왔었음.
		if (bS == 1) continue; //실패.
		if (movN > 10) continue;
		if (rS == 1) {	//성공
			success = true;
			break;
		}

		board[rY][rX] = 'R';
		board[bY][bX] = 'B';

		int canMoveR; //몇 칸 움직일 수 있는지.
		int isDropR; //이동중에 떨어지는지. 떨어지면 1, 아니면 0.
		int canMoveB;
		int isDropB;

		MoveUp(canMoveR, isDropR, rY, rX, 'B');
		MoveUp(canMoveB, isDropB, bY, bX, 'R');
		if ((canMoveR != 0 || canMoveB != 0) && isDropB != 1) {
			quR.push({ { rY - canMoveR, rX }, isDropR });
			quMov.push(movN + 1);
			quB.push({ { bY - canMoveB, bX }, isDropB });
		}
		MoveDown(canMoveR, isDropR, rY, rX, 'B');
		MoveDown(canMoveB, isDropB, bY, bX, 'R');
		if ((canMoveR != 0 || canMoveB != 0) && isDropB != 1) {
			quR.push({ { rY + canMoveR, rX }, isDropR });
			quMov.push(movN + 1);
			quB.push({ { bY + canMoveB, bX }, isDropB });
		}
		MoveLeft(canMoveR, isDropR, rY, rX, 'B');
		MoveLeft(canMoveB, isDropB, bY, bX, 'R');
		if ((canMoveR != 0 || canMoveB != 0) && isDropB != 1) {
			quR.push({ { rY , rX - canMoveR }, isDropR });
			quMov.push(movN + 1);
			quB.push({ { bY , bX - canMoveB }, isDropB });
		}
		MoveRight(canMoveR, isDropR, rY, rX, 'B');
		MoveRight(canMoveB, isDropB, bY, bX, 'R');
		if ((canMoveR != 0 || canMoveB != 0) && isDropB != 1) {
			quR.push({ { rY , rX + canMoveR }, isDropR });
			quMov.push(movN + 1);
			quB.push({ { bY , bX + canMoveB }, isDropB });
		}

		board[rY][rX] = '.';
		board[bY][bX] = '.';
		dp[rY][rX][bY][bX] = 1;

	}
	if (success) cout << movN;
	else cout << "-1";

	return 0;
}

void MoveUp(int& temp, int& isDrop, int Y, int X, char c) {
	temp = 0;
	isDrop = 0;
	bool isBlock = false;  //이동중에 막히는지.
	for (int i = 1; Y - i >= 0 && board[Y - i][X] != '#'; i++) {
		if (board[Y - i][X] == c) { //이동 중에 상대구슬이 있으면 한칸 감소.
			temp--;
			isBlock = true;
		}
		if (board[Y - i][X] == 'O') {
			//if (board[Y - i - 1][X] != '#') isDrop = 1; //벽 옆이 아니거나.
			//else if (isBlock == false) isDrop = 1;	//벽 옆이어도 막히지 않았다면 떨어진다.
			isDrop = 1;
		}
		temp++;
	}
}

void MoveDown(int& temp, int& isDrop, int Y, int X, char c) {
	temp = 0;
	isDrop = 0;
	bool isBlock = false;  //이동중에 막히는지.
	for (int i = 1; Y + i >= 0 && board[Y + i][X] != '#'; i++) {
		if (board[Y + i][X] == c) { //이동 중에 상대구슬이 있으면 한칸 감소.
			temp--;
			isBlock = true;
		}
		if (board[Y + i][X] == 'O') {
			//if (board[Y + i + 1][X] != '#') isDrop = 1; //벽 옆이 아니거나.
			//else if (isBlock == false) isDrop = 1;	//벽 옆이어도 막히지 않았다면 떨어진다.
			isDrop = 1;
		}
		temp++;
	}
}

void MoveLeft(int& temp, int& isDrop, int Y, int X, char c) {
	temp = 0;
	isDrop = 0;
	bool isBlock = false;  //이동중에 막히는지.
	for (int i = 1; X - i >= 0 && board[Y][X - i] != '#'; i++) {
		if (board[Y][X - i] == c) { //이동 중에 상대구슬이 있으면 한칸 감소.
			temp--;
			isBlock = true;
		}
		if (board[Y][X - i] == 'O') {
			//if (board[Y][X - i - 1] != '#') isDrop = 1; //벽 옆이 아니거나.
			//else if (isBlock == false) isDrop = 1;	//벽 옆이어도 막히지 않았다면 떨어진다.
			isDrop = 1;
		}
		temp++;
	}
}

void MoveRight(int& temp, int& isDrop, int Y, int X, char c) {
	temp = 0;
	isDrop = 0;
	bool isBlock = false;  //이동중에 막히는지.
	for (int i = 1; X + i >= 0 && board[Y][X + i] != '#'; i++) {
		if (board[Y][X + i] == c) { //이동 중에 상대구슬이 있으면 한칸 감소.
			temp--;
			isBlock = true;
		}
		if (board[Y][X + i] == 'O') {
			//if (board[Y][X + i + 1] != '#') isDrop = 1; //벽 옆이 아니거나.
			//else if (isBlock == false) isDrop = 1;	//벽 옆이어도 막히지 않았다면 떨어진다.
			isDrop = 1;
		}
		temp++;
	}
}

maeho1459 5년 전 2

저도 22%에서 틀렸었는데

3 8
########
#O...RB#
########

이 케이스가 되도록 수정하니까 통과하더라고요.

yth1130 5년 전 0

그렇군요 ㅠ 정보 감사합니다!

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

문제

문제

출처

ICPC

22%에서 틀렸다고 나오는데 뭐가 문제일까요??

yth1130 5년 전 0

maeho1459 5년 전 2

yth1130 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말