글 읽기 - 안녕하세요 이 문제 좀 해결해 주실 수 있으실까요..?

imonit 5년 전 0

69퍼센트~70퍼센트쯤에서 틀리는데

혹시 같은 고민하신 분 계실까요..?

많은 테스트를 해봐도

반례를 찾기가 너무 어렵네요..

혹시 능력자분께서 부족한 제게 이 문제 반례 좀 찾아주실 수 있으실까요

도움 주신다면 감사하겠습니다

import java.util.Scanner;

public class Main {

	static int N;
	static int M;
	static char [][] map; 
	static int [][] cache;
	
	static Position red;
	static Position blue;
	private static int goal_x = 0, goal_y = 0;
	private static int[][] offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
	
	static void initialize() {
		red = new Position(0, 0, -1);
		blue = new Position(0, 0, -1);	
	}
	
	
	public static int read() {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		String tmp = sc.nextLine();
		cache = new int [N][M];
		map = new char [N][M];

		for(int i = 0; i < N; i++) {
			tmp = sc.nextLine();
			if(tmp == null)
				return -1;
			for(int j = 0; j < M; j++) {
				map[i][j] = tmp.charAt(j);

				if(map[i][j] == 'R') {
					map[i][j] = '.';
					red.xPosition = i;
					red.yPosition = j;
				}
				else if(map[i][j] == 'B') {
					map[i][j] = '.';
					blue.xPosition = i;
					blue.yPosition = j;
				}
				else if(map[i][j] == 'O') {
					goal_x = i;
					goal_y = j;
				}

			}
		}

		return 1;	
	}

	static int priority(Position red, Position blue, int dir) {
		
		if(dir == 0) {
			if(red.xPosition <= blue.xPosition)
				return 1;
			else
				return 0;
		}
		else if(dir == 1) {
			if(red.yPosition >= blue.yPosition)
				return 1;
			else
				return 0;
		}
		else if(dir == 2) {
			if(red.xPosition >= blue.xPosition)
				return 1;
			else
				return 0;
		}
		else {
			if(red.yPosition <= blue.yPosition)
				return 1;
			else 
				return 0;
		}
		
		
		
	}
	
	static Boolean moveable(Position next, char[][]map) {
		
		if(next.xPosition >= N || next.yPosition >= M || next.xPosition < 0 || next.yPosition < 0)
			return false;
		
		if(map[next.xPosition][next.yPosition] == '#')
			return false;
		
		if(map[next.xPosition][next.yPosition] == 'B')
			return false;
		
		else if(map[next.xPosition][next.yPosition] == 'R')
			return false; 
		
		else 
			return true;
	}

	private static void printMap(char[][] new_map) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				System.out.print(new_map[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	static char [][] tilt(Position red, Position blue, int dir, int depth) {
		
		Position next = new Position(0, 0, -1);
		Position p = new Position(0, 0, -1);
		char tmp;
		char [][] new_map = new char [N][M];
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				
				new_map[i][j] = map[i][j];
				
				if(map[i][j] == 'B' || map[i][j] == 'R') {
					new_map[i][j] = '.';
				}
				
			}
		}
		
		int order = priority(red, blue, dir);
		
		
		for(int i = 0; i < 2; i++) {
			
			
			if(order == 1){
				p.xPosition = red.xPosition;
				p.yPosition = red.yPosition;
				tmp = 'R';
			}
			else {
				p.xPosition = blue.xPosition;
				p.yPosition = blue.yPosition;
				tmp = 'B';
			}

			while(true) {

				next.xPosition = p.xPosition + offset[dir][0];
				next.yPosition = p.yPosition + offset[dir][1];

				if(moveable(next, new_map) == false)
					break;
				else if(map[next.xPosition][next.yPosition] == 'O'){

					p.xPosition = next.xPosition;
					p.yPosition = next.yPosition;
					break;
				}

				else {
					p.xPosition = next.xPosition;
					p.yPosition = next.yPosition;
				}
			}
			
			if(map[p.xPosition][p.yPosition] != 'O'){
				new_map[p.xPosition][p.yPosition] = tmp;
			
			}
			
			if(tmp == 'R') {
				red.xPosition = p.xPosition;
				red.yPosition = p.yPosition;
			}
			else {
				blue.xPosition = p.xPosition;
				blue.yPosition = p.yPosition;	
			}
			
			switch(order) {
			case 1:
				order = 0;
				break;
			
			case 0:
				order = 1;
				break;
			}
			
		}
		
		return new_map;
			
	}
	
	static int isThere(char [][] map) {
		
		int t = -1;
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++)
				
				if(t < 0 && map[i][j] == 'R')
					t = 1;
				else if(t >= 0 && map[i][j] == 'R' ||
						t >= 0 && map[i][j] == 'B')
					t = 2;
				else if(t < 0 && map[i][j] == 'B')
					t = 0;
			
			
		}
		
		return t;
		
	}
	
	static int DFS(char[][] map, Position red, Position blue, int depth) {
		
		if(depth > 10)
			return Integer.MAX_VALUE;
		
		int moved = 4000;
		int new_moved = 0;
		
		for(int dir = 0; dir < 4; dir++) {
			
			if(dir == red.prevDir || red.prevDir >= 0 && dir == (red.prevDir + 2)%4)
				continue;
			
			Position new_red = new Position(red.xPosition, red.yPosition, -1);
			Position new_blue = new Position(blue.xPosition, blue.yPosition, -1);
			
			char [][] new_map = tilt(new_red, new_blue, dir, depth);
			
			if(new_red.xPosition == red.xPosition && new_red.yPosition == red.yPosition &&
					new_blue.xPosition == blue.xPosition && new_blue.yPosition == blue.yPosition)
				continue;
			
			int remaining = isThere(new_map);
			
			if(remaining == -1)
				new_moved = -1;
			else if(remaining == 1)
				new_moved = -1;
			else if(remaining == 0)
				return depth;
			else {
				new_red.prevDir = dir;
				moved = Math.min(DFS(new_map, new_red, new_blue, depth+1), moved);
			}
			
		}
		
		if(moved <= 10)
			return moved;
		else
			return Integer.MAX_VALUE;
	}
	
	public static void main(String[] args) {
		initialize();
		read();
		
		int tmp = DFS(map, red, blue, 0);
		if(tmp == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(tmp+1);
		

	}

}

class Position {
	
	
	public int xPosition;
	public int yPosition;
	public int prevDir;
	
	public Position(int a, int b, int c) {
		xPosition = a;
		yPosition = b;
		prevDir = c;
	}
	
}

djm03178 5년 전 3

11이 출력되는 경우가 있습니다.

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

imonit 5년 전 0

L 아 정말 감사합니다.

덕분에 뭘 잘못했는 지 아는데에 정말정말 큰 도움이 됐어요

능력자님처럼 저도 노력해서 다른 분들께 도움이 되도록하겠습니다!

진심으로 감사드려요

저도 능력자님께 꼭 언젠가 도움이 될 수 있음 좋겠습니다

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

문제

문제

출처

ICPC

안녕하세요 이 문제 좀 해결해 주실 수 있으실까요..?

imonit 5년 전 0

djm03178 5년 전 3

imonit 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말