글 읽기 - 구슬탈출2 예외 케이스 질문이 있습니다.

ng2111 2년 전 0

게시판에 있는 많은 테스트케이스를 시도해보았지만 시도해본 케이스는 다 통과해서 답답한 마음에 질문해봅니다.

혹시 코드에 잘못된 부분이나 예외케이스가 있을경우 알려주시면 감사하겠습니다.

#include <stdio.h>
#include <string.h>
#include <queue>
#include<algorithm>
using namespace std;


int MINIMUM = 11;
int dx[4] = { 1,0,-1,0 }; // 0 :R // 1 : D // 2 : L // 4 : U
int dy[4] = { 0,1,0,-1 };
int n, m;

char arr[11][11];
void dfs(int count, pair<int, int> Ballpos[2] , bool visited[11][11][11][11]) {
	if (count > 10) {// 10번 넘어가면 -1
		if (MINIMUM > 10) {
			MINIMUM = -1;
		}
		return;
	}
	else {
		if (arr[Ballpos[0].first][Ballpos[0].second] == 'O' &&arr[Ballpos[1].first][Ballpos[1].second] != 'O') {//빨간공만 통과했을때 횟수 계산
			if (MINIMUM == -1) 
				MINIMUM = count;
			
			else if(MINIMUM > count)
				MINIMUM = count;
			return;
		}
		if (arr[Ballpos[1].first][Ballpos[1].second] == 'O') {// 파란구슬 통과했을 때 -1
			if (MINIMUM > 10) {
				MINIMUM = -1;
			}
			return;
		}
	
	}
	pair<int, int>temp[2]; /// 0 : 빨간공 위치 1 : 파란공 위치 복사
	temp[0].first = Ballpos[0].first;
	temp[0].second = Ballpos[0].second;
	temp[1].first = Ballpos[1].first;
	temp[1].second = Ballpos[1].second;
	bool tempvisited[11][11][11][11]; /// 방문위치 복사
	for (int i = 0; i < 11; i++)
	{
		for (int j = 0; j < 11; j++)
		{
			for (int k = 0; k < 11; k++)
			{
				for (int l = 0; l < 11; l++)
				{
					tempvisited[i][j][k][l] = visited[i][j][k][l];
				}
			}
		}
	}
	for (int i = 0; i < 4; i++)//0 : R / 1 : D / 2 : L / 3: U
	{
		int ry = Ballpos[0].first ;
		int rx = Ballpos[0].second ;
		int by = Ballpos[1].first ;
		int bx = Ballpos[1].second;
		if (ry + dy[i] >= 0 && rx + dx[i] >= 0 && by + dy[i] >= 0 && bx + dx[i] >= 0 && ry + dy[i] < n && rx + dx[i]< m && by + dy[i] < n && bx + dx[i]< m) { /// 보드 범위 안에서 움직이도록
			while (arr[ry + dy[i]][rx + dx[i]] != '#' ) {///벽만날 때 까지
				ry += dy[i];
				rx += dx[i];
				if (arr[ry][rx] == 'O')/// 목적지 만났을때
					break;
			}
			while (arr[by + dy[i]][bx + dx[i]] != '#' ) {/// 마찬가지로 벽만날 때까지
				by += dy[i];
				bx += dx[i];
				if (arr[by][bx] == 'O')
					break;
			}
			if (ry == by && rx == bx) { /// 같은위치에 도달했을때
				if (arr[by][bx] == 'O') {
					printf("");
				}
				else { /// 먼거리에서 온 구슬이 한칸 뒤로
					if (abs(ry - Ballpos[0].first) + abs(rx - Ballpos[0].second) > abs(by - Ballpos[1].first) + abs(bx - Ballpos[1].second)) {
						ry -= dy[i];
						rx -= dx[i];
					}
					else {
						by -= dy[i];
						bx -= dx[i];
					}
				}
				
			}
		}
		else {
			continue;
		}

		if (visited[ry][rx][by][bx] == 0) { /// 방문체크
			tempvisited[ry][rx][by][bx] = 1;
			temp[0].first = ry;
			temp[0].second = rx;
			temp[1].first = by;
			temp[1].second = bx;
			
		
			if (MINIMUM != -1 && MINIMUM < count)
				return;
			dfs(count + 1, temp, tempvisited);
			//0 : R / 1 : D / 2 : L / 3: U
		}
		
	}
	
}
int main() {
	scanf("%d %d", &n, &m);
	memset(arr, 0, sizeof(arr));
	pair<int, int> O;
	pair<int, int> Ballpos[2];

	bool visited[11][11][11][11] = { false, };
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			char input;
			scanf("\n%c", &input);
			if (input == 'R') {
				Ballpos[0].first = i;
				Ballpos[0].second = j;
				arr[i][j] = input;
			}
			else if (input == 'O') {
				O.first = i;
				O.second = j;
				arr[i][j] = input;
			}
			else if (input == 'B') {
				Ballpos[1].first = i;
				Ballpos[1].second = j;
				arr[i][j] = input;
			}
			else {
				arr[i][j] = input;
			}
		}
	}
	visited[Ballpos[0].first][Ballpos[0].second][Ballpos[1].first][Ballpos[1].second] = true;

	dfs(0, Ballpos, visited);

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

djm03178 2년 전 1

반례 드립니다.

10 10
##########
#..##..###
##########
###..#####
########.#
#.###O...#
#B.##..###
##.##.####
##.#.##R##
##########
output: 11
correct answer: -1

10 10
##########
##.##..B.#
###R####.#
#.###O.###
##.##....#
#####..#.#
#.###.####
#.###..#.#
######.###
##########
output: 11
correct answer: -1

10 9
#########
#########
##B#.####
#.#######
##.####.#
###.##O##
#######.#
##.R#.#.#
###.#####
#########
output: 11
correct answer: -1

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

문제

문제

출처

ICPC

구슬탈출2 예외 케이스 질문이 있습니다.

ng2111 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말