글 읽기 - 예시답변과 질문답변란에 있는 예시들 다 맞았는데 틀렸다고 뜹니다ㅠ

saera1111 5년 전 0

내용 그대로 입니다ㅠㅠ

질문답변란에 있는 모든 예시들은 통과했습니다

여러가지 테스트 케이스를 생각해봤지만 자꾸 초반부터 틀렸다고만 뜨네요..

혹시 헛점이나 반례가 보이신다면 꼭 답변 부탁드리겠습니다!ㅠㅠ

#include <iostream>
#include <algorithm>
using namespace std;

int fail = 987654321;

int N, M;
char map[20][20] = { 0, };	//일단 테스트를 위해 맵 크기를 키움
int R[2] = { 0, };	//R(빨간공)의 좌표
int B[2] = { 0, };	//B(파란공)의 좌표

//0:북 1:동 2:남 3:서
int ax[4] = { -1, 0, 1, 0 };
int ay[4] = { 0, 1, 0, -1 };


int dfs(int cnt) {
	
	//10번 초과로 기울일 경우 실패
	if (cnt >= 10)
		return fail;

	int r = fail;	//return 할 값 (처음엔 큰 값으로 초기화)
	bool r_inHole = false, b_inHole = false;	//각각 빨간공, 파란공이 구멍에 들어갔을 때 true

	//후에 리셋을 위한 변수들
	int Rx = R[0], Ry = R[1];
	int Bx = B[0], By = B[1];
	int dx, dy;

    //4 방향 모두 체크
	for(int i = 0; i < 4; i++) {
		///////////////////////////
		//R이 먼저 움직여야 할 상황
		if ((i == 0 && Rx < Bx) || (i == 1 && Ry > By) || (i == 2 && Rx > Bx) || (i == 3 && Ry < By)) {
			//R을 움직인다
			while (1) {
				//다음 칸 이동
				dx = R[0] + ax[i]; dy = R[1] + ay[i];

				//벽일 경우 그 자리에서 break
				if (map[dx][dy] == '#') {
					break;
				}
				//구멍일 경우
				if (map[dx][dy] == 'O') {
					//-1로 이동시킨 후(구멍이 막히지 않도록) check
					R[0] = -1; R[1] = -1;
					r_inHole = true;
					break;
				}

				R[0] = dx; R[1] = dy;
			}

			//B를 움직인다
			while (1) {
				//다음 칸 이동
				dx = B[0] + ax[i]; dy = B[1] + ay[i];

				//벽이나 빨간 구슬일 경우 그 자리에서 break
				if (map[dx][dy] == '#' || (dx == R[0] && dy == R[1]))
					break;
				//구멍일 경우
				if (map[dx][dy] == 'O') {
					//check
					b_inHole = true;
					break;
				}
				B[0] = dx; B[1] = dy;
			}
		}

		///////////////////////////
		//B가 먼저 움직여야 할 상황
		else {
			//B를 움직인다
			while (1) {
				//다음 칸 이동
				dx = B[0] + ax[i]; dy = B[1] + ay[i];

				//벽일 경우 break
				if (map[dx][dy] == '#')
					break;
				//구멍일 경우
				if (map[dx][dy] == 'O') {
					//-1로 이동시킨 후(구멍이 막히지 않도록) check
					B[0] = -1; B[1] = -1;
					b_inHole = true;
					break;
				}
				B[0] = dx; B[1] = dy;
			}
			//R을 움직인다
			while (1) {
				//다음 칸 이동
				dx = R[0] + ax[i]; dy = R[1] + ay[i];

				//벽일 경우 break
				if (map[dx][dy] == '#' || (dx == B[0] && dy == B[1])) {
					break;
				}
				//구멍일 경우
				if (map[dx][dy] == 'O') {
					//check
					r_inHole = true;
					break;
				}

				R[0] = dx; R[1] = dy;
			}

		}

		/////////////////////////
		//기울인 후 공의 상태 체크
		//파란 구슬이 들어간 경우
		if (b_inHole) {
			//공들을 기울이기 바로 전의 위치로 리셋 && flag들 리셋
			R[0] = Rx; R[1] = Ry;
			B[0] = Bx; B[1] = By;
			b_inHole = false;
			r_inHole = false;

			r = min(r, fail);
		}
		//빨간 구슬만 들어간 경우
		else if ((!b_inHole) && r_inHole) {
			//공들을 기울이기 바로 전의 위치로 리셋 && flag들 리셋
			R[0] = Rx; R[1] = Ry;
			B[0] = Bx; B[1] = By;
			b_inHole = false;
			r_inHole = false;

			r = min(r, cnt);
		}
		//둘 다 아닌 경우
		else {	
			r = min(r, dfs(cnt + 1));
			R[0] = Rx; R[1] = Ry;
			B[0] = Bx; B[1] = By;
			r_inHole = false;
			b_inHole = false;
		}
	}

	return r;

}

int main() {
	int r = 0;

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++){
			cin >> map[i][j];
			if (map[i][j] == 'R') {
				R[0] = i;
				R[1] = j;
			}
			else if (map[i][j] == 'B') {
				B[0] = i;
				B[1] = j;
			}
		} 
	}
	/////입력 끝

	r = dfs(1);
	if (r == fail)
		r = -1;

	//결과 출력
	cout << r << endl;

	return 0;
}

djm03178 5년 전 3

랜덤 생성기 만든 김에 찾아드렸습니다.

9 7
#######
#.....#
#.....#
#R....#
#.....#
##...B#
#.....#
#..O..#
#######
correct = -1, wrong = 3

9 6
######
#...##
##..O#
##R.B#
#.#.##
#...##
###..#
#.#..#
######
correct = 4, wrong = 6

8 7
#######
#.....#
#.....#
####.O#
##..R##
###..##
#...B.#
#######
correct = 4, wrong = 3

9 6
######
##..B#
#.#..#
#....#
#...O#
#....#
#.#..#
#R.#.#
######
correct = -1, wrong = 4

10 6
######
#..#.#
#.R..#
#.B..#
#.O..#
#...##
#....#
##...#
#....#
######
correct = 3, wrong = 1

6 6
######
#B#..#
#.####
#.#..#
#OR.##
######
correct = 1, wrong = -1

10 8
########
#...#.##
##.##.##
##..##.#
#...##.#
#O..#.##
#.#.#..#
#R.###.#
#B.#...#
########
correct = -1, wrong = 5

8 9
#########
#..B....#
#.......#
#.......#
#.....O.#
#..#....#
#...#R..#
#########
correct = -1, wrong = 8

6 8
########
##..#O.#
#.##.B.#
#.#...R#
#...##.#
########
correct = 4, wrong = -1

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

문제

문제

출처

ICPC

예시답변과 질문답변란에 있는 예시들 다 맞았는데 틀렸다고 뜹니다ㅠ

saera1111 5년 전 0

djm03178 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말