글 읽기 - 13460 째로탈출2 반례 좀 부탁드립니다 ㅜㅜㅜ;;;

rzh1008 5년 전 0

소스 코드가 굉장히 깁니다...ㅠㅠ;;;
게시판에 있는 테스트 케이스들 다 조사해서 넣어봐도 제대로 정답을 출력하는데
채점만 하면 1%를 넘어가지 못하고 틀리네요...ㅜㅜ;;; 뭐가 문제일까요??? 좋은 반례 테스트 케이스 있으면 좀 부탁드리겠습니다 ㅜㅜ;;;
import java.util.*;

public class Main {
	public static int answer,n,m;
	public static char[][] copyMap(char[][] parameterMap) {
		char[][] copiedMap = new char[n][m];
		for (int i=0; i<n; i++) {
			for (int j=0; j<m; j++) {
				copiedMap[i][j] = parameterMap[i][j];
			}
		}
		return copiedMap;
	}
	public static void dfs(int depth, int prx, int pry, int pbx, int pby, char[][] passedMap) {
		if (depth==11) return;
		for (int d=0; d<4; d++) {
			char[][] map = copyMap(passedMap);
			if (d==0) {
				int rx=prx, ry=pry, bx=pbx, by=pby;
				// 위로
				if (ry<by) {
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[ry-1][rx]=='.') {
							map[ry-1][rx] = 'R';
							map[ry][rx] = '.';
							ry--;
						}
						else if (map[ry-1][rx]=='O') {
							rFlag = true;
							map[ry][rx]='.';
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[by-1][bx]=='.') {
							map[by-1][bx] = 'B';
							map[by][bx] = '.';
						by--; }
						else if (map[by-1][bx]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				} else {
					// R이 밑에 있거나 같은 라인에 있음
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[by-1][bx]=='.') {
							map[by-1][bx] = 'B';
							map[by][bx] = '.'; by--;
						}
						else if (map[by-1][bx]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[ry-1][rx]=='.') {
							map[ry-1][rx] = 'R';
							map[ry][rx] = '.';
							ry--;
						}
						else if (map[ry-1][rx]=='O') {
							rFlag = true;
							break;
						}
						else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				}
			} else if (d==1) {
				int rx=prx, ry=pry, bx=pbx, by=pby;
				// 오른쪽으로
				if (rx>bx) {
					// R이 오른쪽에 있음
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[ry][rx+1]=='.') {
							map[ry][rx+1] = 'R';
							map[ry][rx] = '.';
							rx++;
						}
						else if (map[ry][rx+1]=='O') {
							rFlag = true;
							map[ry][rx]='.';
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[by][bx+1]=='.') {
							map[by][bx+1] = 'B';
							map[by][bx] = '.';
							bx++;
						}
						else if (map[by][bx+1]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				} else {
					// R이 왼쪽에 있거나 같은 라인에 있음
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[by][bx+1]=='.') {
							map[by][bx+1] = 'B';
							map[by][bx] = '.';
							bx++;
						}
						else if (map[by][bx+1]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[ry][rx+1]=='.') {
							map[ry][rx+1] = 'R';
							map[ry][rx] = '.';
							rx++;
						} else if (map[ry][rx+1]=='O') {
							rFlag = true;
							break;
						} else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				}
			} else if (d==2) {
				int rx=prx, ry=pry, bx=pbx, by=pby;
				// 아래로
				if (ry>by) {
					// R이 밑에 있음
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[ry+1][rx]=='.') {
							map[ry+1][rx] = 'R';
							map[ry][rx] = '.';
							ry++;
						}
						else if (map[ry-1][rx]=='O') {
							rFlag = true;
							map[ry][rx]='.';
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[by+1][bx]=='.') {
							map[by+1][bx] = 'B';
							map[by][bx] = '.';
							by++;
						}
						else if (map[by+1][bx]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				} else {
					// R이 위에 있거나 같은 라인에 있음
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[by+1][bx]=='.') {
							map[by+1][bx] = 'B';
							map[by][bx] = '.';
							by++;
						}
						else if (map[by+1][bx]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[ry+1][rx]=='.') {
							map[ry+1][rx] = 'R';
							map[ry][rx] = '.';
							ry++;
						}
						else if (map[ry+1][rx]=='O') {
							rFlag = true;
							break;
						}
						else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				}
			} else if (d==3) {
				int rx=prx, ry=pry, bx=pbx, by=pby;
				// 왼쪽으로
				if (rx<bx) {
					// R이 왼쪽에 있음
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[ry][rx-1]=='.') {
							map[ry][rx-1] = 'R';
							map[ry][rx] = '.';
							rx--;
						}
						else if (map[ry][rx-1]=='O') {
							map[ry][rx] = '.';
							rFlag = true;
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[by][bx-1]=='.') {
							map[by][bx-1] = 'B';
							map[by][bx] = '.';
							bx--;
						}
						else if (map[by][bx-1]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				} else {
					// R이 오른쪽에 있거나 같은 라인에 있음
					boolean rFlag=false, bFlag = false;
					// R이 위에 있음
					while(true) {
						if (map[by][bx-1]=='.') {
							map[by][bx-1] = 'B';
							map[by][bx] = '.';
							bx--;
						}
						else if (map[by][bx+1]=='O') {
							bFlag = true;
							break;
						}
						else {
							break;
						}
					}
					while(true) {
						if (map[ry][rx-1]=='.') {
							map[ry][rx-1] = 'R';
							map[ry][rx] = '.';
							rx--;
						}
						else if (map[ry][rx-1]=='O') {
							rFlag = true;
							break;
						}
						else {
							break;
						}
					}
					if (rFlag&&!bFlag) {
						answer = Math.min(answer, depth+1);
						return;
					}
					if (!rFlag&&!bFlag) {
						dfs(depth+1,rx,ry,bx,by,map);
					}
					else {
						continue;
					}
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		answer = Integer.MAX_VALUE;
		n = scanner.nextInt(); m = scanner.nextInt();
		char[][] originalMap = new char[n][m];
		int rx=0,ry=0,bx=0,by=0;
		scanner.nextLine();
		for (int i=0; i<n; i++) {
			String str = scanner.nextLine();
			for (int j=0; j<m; j++) {
				originalMap[i][j] = str.charAt(j);
				if (originalMap[i][j]=='R') {
					rx=j; ry=i;
				}
				if (originalMap[i][j]=='B') {
					bx=j; by=i;
				}
			}
		}
		
		dfs(0,rx,ry,bx,by, originalMap);
		if (answer>10) answer=-1;
		System.out.printf("%d",answer);
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

13460 째로탈출2 반례 좀 부탁드립니다 ㅜㅜㅜ;;;

rzh1008 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말
