글 읽기 - 반례좀 찾아주실수 있을까요..ㅠ 도저히 모르겠네요..

aod0326 4년 전 0

어떤부분이 틀렸다는지 도저히 모르겠네요..

나름 질문게시판에 올라온 반례들 다 통과 시켰는데 안되네요..ㅜㅜㅜㅜㅜ

도와주세요 ㅠ

#include <iostream>
#include <queue>
using namespace std;
class PosInfo {
public:
	int r_x, r_y, b_x, b_y, move, dir;
	// way => 1 = 아래, 2 = 오, 3 = 위, 4 = 왼
	PosInfo(int r_x, int r_y, int b_x, int b_y, int move, int dir) {
		this->r_x = r_x;
		this->r_y = r_y;
		this->b_x = b_x;
		this->b_y = b_y;
		this->move = move;
		this->dir = dir;
	}
};
char map[11][11];
bool visited[11][11][11][11];
int xpos[] = { -1, 0, 1, 0 };
int ypos[] = { 0, 1, 0, -1 };
int move(PosInfo &p) {
	bool isR_zero = false;
	bool isB_zero = false;
	while (true) {
		int x1 = p.r_x, x2 = p.b_x, y1 = p.r_y, y2 = p.b_y;
		if (p.dir == 1) { x1--; x2--; }
		else if (p.dir == 2) { y1++; y2++; }
		else if (p.dir == 3) { x1++; x2++; }
		else { y1--; y2--; }

		// 둘다 벽이면 break;
		if (map[x1][y1] == '#' && map[x2][y2] == '#') break;

		// 지난 자리에 구멍이 있었는지 check
		if (map[x1][y1] == 'O') isR_zero = true;
		if (map[x2][y2] == 'O') isB_zero = true;

		// 만약 벽이면 변화된 좌표 원상복구
		if (map[x1][y1] == '#') { x1 = p.r_x; y1 = p.r_y; }
		if (map[x2][y2] == '#') { x2 = p.b_x; y2 = p.b_y; }

		// 벽이 아니고 두 구슬이 겹치지 않을 때 좌표 이동
		if (map[x1][y1] != '#' && !(x1 == x2 && y1 == y2)) {
			p.r_x = x1; p.r_y = y1;
		}
		if (map[x2][y2] != '#' && !(x1 == x2 && y1 == y2)) {
			p.b_x = x2; p.b_y = y2;
		}

		// 두 구슬이 겹치면 break;
		if (x1 == x2 && y1 == y2)
			break;
	}

	// 빨강만 나가면 1
	if (isR_zero && !isB_zero) return 1;
	// 둘다 나가거나 파랑이 나가면 -1
	else if (isR_zero || isB_zero) return -1;
	else return 0;
}
int bfs(PosInfo start, int n, int m) {
	queue<PosInfo> q;
	for (int i = 1; i <= 4; i++) {
		PosInfo pos = start;
		pos.dir = i;
		q.push(pos);
	}
	visited[start.r_x][start.r_y][start.b_x][start.b_y] = true;
	while (!q.empty()) {
		PosInfo pos = q.front();
		q.pop();
		int result = move(pos);
		if (result == 1 && !visited[pos.r_x][pos.r_y][pos.b_x][pos.b_y]) {
			return pos.move + 1;
		}
		else {
			// move의 결과가 0일 경우와 빨강, 파란공 위치가 이전에 없었던 위치면 q에 추가
			if (!visited[pos.r_x][pos.r_y][pos.b_x][pos.b_y] && result == 0) {
				visited[pos.r_x][pos.r_y][pos.b_x][pos.b_y] = true;
				PosInfo temp = pos;
				temp.move++;
				for (int i = 1; i <= 4; i++) {
					if (pos.dir != i) {
						temp.dir = i;
						q.push(temp);
					}
				}
			}
		}
	}
	return -1;
}
int main(void) {
	int n, m;
	cin >> n >> m;
	pair<int, int> r_pos, b_pos;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'R') r_pos = { i, j };
			if (map[i][j] == 'B') b_pos = { i, j };
		}
	}
	int result = bfs(PosInfo(r_pos.first, r_pos.second, b_pos.first, b_pos.second, 0, 0), n, m);
	if (result <= 10) cout << result;
	else cout << -1;
	return 0;
}

clrmt 4년 전 0

우연히 이걸 대입했더니 -1이 나옵니다. 답은 2입니다.

4 6
######
#R..B#
#.O.##
######

aod0326 4년 전 0

오오.. 감사합니다 !!

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

문제

문제

출처

ICPC

반례좀 찾아주실수 있을까요..ㅠ 도저히 모르겠네요..

aod0326 4년 전 0

clrmt 4년 전 0

aod0326 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말