글 읽기 - dfs로 풀었는데 어떤 테스트케이스에서 걸리는지 모르겠습니다 ㅠㅠ

MrSeo 5년 전 0

어느 테스트케이스에서 걸리는지 모르겠습니다 ㅠㅠ

반례 알려주실 수 있나요....

#include <iostream>
#define N 11
class dot {
public:
	int x, y;
};
int min = -1;
int n, m;
char map[N][N];

int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

void dfsRecursive(dot R, dot B, int n) {
	if (n >= 10 || (min != -1 && n > min)) return;
	for (int i = 0; i < 4; i++) {
		dot tR = R, tB = B;
		map[tR.y][tR.x] = 'R';
		map[tB.y][tB.x] = 'B';

		bool check = false;
		while (map[tR.y + dy[i]][tR.x + dx[i]] == '.' || map[tB.y + dy[i]][tB.x + dx[i]] == '.') {
			check = true;
			while (map[tR.y + dy[i]][tR.x + dx[i]] == '.') {
				map[tR.y][tR.x] = '.';
				tR.y = tR.y + dy[i], tR.x = tR.x + dx[i];
				map[tR.y][tR.x] = 'R';
			}
			while (map[tB.y + dy[i]][tB.x + dx[i]] == '.') {
				map[tB.y][tB.x] = '.';
				tB.y = tB.y + dy[i], tB.x = tB.x + dx[i];
				map[tB.y][tB.x] = 'B';
			}
		}

		if (map[tR.y + dy[i]][tR.x + dx[i]] == 'O') {
			if (map[tR.y + dy[i] * 2][tR.x + dx[i] * 2] != '#' && map[tR.y - dy[i]][tR.x - dx[i]] == 'B') {
				map[tR.y][tR.x] = '.';
				map[tB.y][tB.x] = '.';
				continue;
			}
			map[tR.y][tR.x] = '.';
			map[tB.y][tB.x] = '.';
			if(min == -1 || min > n + 1) min = n + 1;
			return;
		}
		else if (map[tB.y + dy[i]][tB.x + dx[i]] == 'O') {
			map[tR.y][tR.x] = '.';
			map[tB.y][tB.x] = '.';
			continue;
		}
		map[tR.y][tR.x] = '.';
		map[tB.y][tB.x] = '.';
		if (check) dfsRecursive(tR, tB, n + 1);
	}
}
int main() {
	dot R, B;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == '.' || map[i][j] == '#' || map[i][j] == 'O') continue;
			else if (map[i][j] == 'R') {
				R.x = j, R.y = i;
				map[i][j] = '.';
			}
			else if (map[i][j] == 'B') {
				B.x = j, B.y = i;
				map[i][j] = '.';
			}
		}

	dfsRecursive(R, B, 0);

	printf("%d\n", min);
	return 0;
}

jh05013 5년 전 0

질문 검색을 누르면 반례가 달린 글이 나옵니다.

MrSeo 5년 전 0

질문 검색에 있는 테스트 케이스를 다 돌려봤습니다.. 제가 22프로 가는 도중에 틀렸다고 떠서 비슷한 퍼센트에서 걸리신다는
3 8
########
#O...RB#
########
정답 : 1
도 이미 처리를 해둔 상태였습니다...
어디에 문제가 있는걸까요...

jh05013 5년 전 1

정답은 -1입니다.

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

문제

문제

출처

ICPC

dfs로 풀었는데 어떤 테스트케이스에서 걸리는지 모르겠습니다 ㅠㅠ

MrSeo 5년 전 0

jh05013 5년 전 0

MrSeo 5년 전 0

jh05013 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말