글 읽기 - 예시와 질분하기의 반례 다 돌려봤는데...다른반례부탁드립니다ㅜㅜ

haepen1 5년 전 0

질문하기에있는 반례와 예시들을 다 돌려봤는데...
다른 반례없을까요?ㅜㅜ

import java.io.*;
public class Main{
	public static int N,M,rx,ry,bx,by,min;
	public static char[][] arr;
	public static boolean[][][][] visited;
	public static void main(String[] args)throws IOException{
		//BufferedReader br = new BufferedReader(new FileReader("input"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] size = br.readLine().split(" ");
		N = Integer.parseInt(size[0]);
		M = Integer.parseInt(size[1]);
		arr = new char[N][M];
		visited = new boolean[11][11][11][11];
		for(int i=0; i<N; i++){
			String str = br.readLine().trim();
			for(int j=0; j<M; j++){
				arr[i][j] = str.charAt(j);
				//System.out.print(arr[i][j]);
				if(arr[i][j]=='R'){
					rx = i;
					ry = j;
				}if(arr[i][j]=='B'){
					bx = i;
					by = j;
				}
			}//System.out.println();
		}
		min = Integer.MAX_VALUE;
		DFS(rx,ry,bx,by,0);
		if(min==Integer.MAX_VALUE){
			System.out.println(-1);
		}else{
			System.out.print(min);
		}
	}
	public static void DFS(int rx, int ry, int bx, int by,int cnt){
		int[] dx = {-1,1,0,0}; //상하좌우
		int[] dy = {0,0,-1,1}; //상하좌우
		visited[rx][ry][bx][by] = true;
		if(cnt>10){
			//min = -1;
			return;
		}
		for(int i=0; i<4; i++){
			boolean flag = false;
			int rax=rx,ray=ry,bax=bx,bay=by;
			while(isInRange(bax+dx[i],bay+dy[i])==0 && arr[bax+dx[i]][bay+dy[i]]!='#'&& arr[bax+dx[i]][bay+dy[i]]!='O'){
				bax = bax+dx[i];
				bay = bay+dy[i];
				if(arr[bax+dx[i]][bay+dy[i]]=='O'){
					flag = true;
				}	
			}
			if(arr[bax+dx[i]][bay+dy[i]]=='O'){
				flag = true;
			}	
			while(isInRange(rax+dx[i],ray+dy[i])==0 && arr[rax+dx[i]][ray+dy[i]]!='#'&& arr[rax+dx[i]][ray+dy[i]] !='O'){
				rax = rax+dx[i];
				ray = ray+dy[i];
				if(arr[rax+dx[i]][ray+dy[i]]=='O'){
					if(flag == false){
						cnt++;
						//System.out.println("red OUT"+cnt);
						min = Math.min(min, cnt);
						return;
					}else if(flag == true){
					//	System.out.println("blue Also OUT"+"-1");
						return;
					}
				}
			}
			
			if(flag==false && arr[rax+dx[i]][ray+dy[i]]=='O'){
				cnt++;
				min = Math.min(min, cnt);
				return;
			}
			
			if(rax==bax&&ray==bay){
				if(i==0){//상
					if(rx<bx){bax=bax+1;}
					else{rax=rax+1;}
				} if(i==1){//하
					if(rx<bx){rax=rax-1;}
					else{bax=bax-1;};
				}if(i==2){ //좌
					if(ry<by){bay=bay+1;}
					else{ray=ray+1;} 
				}if(i==3){//우
					if(ry<by){ray=ray-1;}
					else{bay=bay-1;}
				}
			}
			
			if(visited[rax][ray][bax][bay] == false && flag==false){
				visited[rax][ray][bax][bay] = true;
				DFS(rax,ray,bax,bay,cnt+1);
				visited[rax][ray][bax][bay] = false;
				
			}
		
		}
	}
	public static int isInRange(int a, int b){
		if(0<=a&&a<N && 0<=b&&b<M){
			return 0;
		}else return 1;
	}
}

djm03178 5년 전 6

여기 드립니다.

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

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

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

haepen1 5년 전 0

감사합니다!!ㅠㅠㅠㅠ

lmiz 5년 전 0

세번째 반례 아래처럼 움직일 수 있는건 아닌가요?? 제가 어떤부분을 이해하지 못하고 있는건가요 ??

#########
###.....#
#..#..#O#
##..R.#B#
####....#
#.....#.#
#.#.....#
##.###..#
#########
1
#########
###.....#
#..#..#O#
##....#.#
####....#
#.....#.#
#.#.R...#
##.###.B#
#########
2
#########
###.....#
#..#..#O#
##....#.#
####....#
#.....#.#
#.#R....#
##.###B.#
#########
3
#########
###.....#
#..#..#O#
##....#.#
####....#
#..R..#.#
#.#...B.#
##.###..#
#########
4
#########
###.....#
#..#..#O#
##....#.#
####....#
#R....#.#
#.#B....#
##.###..#
#########
5
#########
###.....#
#..#..#O#
##....#.#
####....#
#R.B..#.#
#.#.....#
##.###..#
#########
6
#########
###.....#
#..#..#O#
##....#.#
####....#
#...RB#.#
#.#.....#
##.###..#
#########
7
#########
###.RB..#
#..#..#O#
##....#.#
####....#
#.....#.#
#.#.....#
##.###..#
#########
8
#########
###RB...#
#..#..#O#
##....#.#
####....#
#.....#.#
#.#.....#
##.###..#
#########
9
#########
###R....#
#..#..#O#
##....#.#
####....#
#.....#.#
#.#.B...#
##.###..#
#########
10
#########
###....R#
#..#..#O#
##....#.#
####....#
#.....#.#
#.#....B#
##.###..#
#########
11

djm03178 5년 전 4

"만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다."

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

문제

문제

출처

ICPC

예시와 질분하기의 반례 다 돌려봤는데...다른반례부탁드립니다ㅜㅜ

haepen1 5년 전 0

djm03178 5년 전 6

haepen1 5년 전 0

lmiz 5년 전 0

djm03178 5년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말