글 읽기 - 도무지 반례를 못찾겠습니다 ! 도와주세요!

minhye11 4년 전 0

BFS로 풀었습니다. 그리고 -1이 출력되는 경우에는 시간이 좀 걸리던데 이거 코드를 맞게 고치더라도 시간초과가 뜰까요?

#include <iostream> 
#include <queue>
using namespace std;
int N, M;
int a, b, c, d;
char board[10][11];
queue <int> x;
queue <int> y;
queue <int> x2;
queue <int> y2;
queue <int> counts;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };


int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> board[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 'R') {
				a = i;
				b = j;
				board[i][j] = '.';
			}
			if (board[i][j] == 'B') {
				c = i;
				d = j;
				board[i][j] = '.';
			}
		}
	}

	x.push(a);
	y.push(b);
	x2.push(c);
	y2.push(d);
	counts.push(0);

	while (counts.front() < 10) {
		for (int i = 0; i < 4; i++) {
			int v1 = x.front();
			int w1 = y.front();
			int v2 = x2.front();
			int w2 = y2.front();
			int c = counts.front();

			while (true) {

				int nx1 = v1 + dx[i];
				int ny1 = w1 + dy[i];
				int nx2 = v2 + dx[i];
				int ny2 = w2 + dy[i];
				if (board[nx1][ny1] == '#' && board[nx2][ny2] == '#') {/*둘 다 벽을 만났따*/
					x.push(v1);
					y.push(w1);
					x2.push(v2);
					y2.push(w2);
					counts.push(c + 1);
					break;
				}
				if (board[nx1][ny1] == '#' && nx2 + dx[i] == nx1 && ny2 + dy[i] == ny1) {/*벽 - R - B*/
					x.push(v1);
					y.push(w1);
					x2.push(v2);
					y2.push(w2);
					counts.push(c + 1);
					break;
				}
				if (board[nx2][ny2] == '#' && nx1 + dx[i] == nx2 && ny1 + dy[i] == ny2) {/*벽 - B - R*/
					x.push(v1);
					y.push(w1);
					x2.push(v2);
					y2.push(w2);
					counts.push(c + 1);
					break;
				}

				/*이제 빠져나가는 경우를 봅싀당*/
				if (board[nx2][ny2] == 'O') {
					break;
				}
				if (board[nx1][ny1] == 'O') {
					while (1) {
						if (board[nx2][ny2] == 'O') {
							break;
						}
						nx2 += dx[i];
						ny2 += dy[i];
						if (board[nx2][ny2] == '#') {
							cout << c + 1;
							return 0;
						}
					}
					break;
				}
				/*이동할 칸이 남어따*/
				if (board[nx1][ny1] != '#') {
					v1 += dx[i];
					w1 += dy[i];
				}
				if (board[nx2][ny2] != '#') {
					v2 += dx[i];
					w2 += dy[i];
				}
			}
		}
		x.pop();
		y.pop();
		x2.pop();
		y2.pop();
		counts.pop();
	}

	cout << -1;
	return 0;

}

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

문제

문제

출처

ICPC

도무지 반례를 못찾겠습니다 ! 도와주세요!

minhye11 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말