import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
class Ball {
int y, x;
static int MapSize_Y;
static int MapSize_X;
static int holeY;
static int holeX;
public Ball(int y, int x) {
this.y = y;
this.x = x;
Main.Map[y][x] = 'X'; // 공의 위치 표기
}
public void move(int rIndex) {
int tempY = y;
int tempX = x;
int moveY = y + Main.rotY[rIndex];
int moveX = x + Main.rotX[rIndex];
// 한 방향으로 직진
while (isRight(moveY, moveX)) {
// 성공좌표를 저장 한다.
y = moveY;
x = moveX;
// 전진
moveY += Main.rotY[rIndex];
moveX += Main.rotX[rIndex];
}
// 공의 위치를 변경한다.
Main.Map[tempY][tempX] = '.';
Main.Map[y][x] = isHoll() ? 'O' : 'X';
}
public void move(int inputY, int inputX) {
Main.Map[this.y][this.x] = isHoll() ? 'O' : '.';
this.y = inputY;
this.x = inputX;
Main.Map[this.y][this.x] = isHoll() ? 'O' : 'X';
}
public boolean isRight(int inputY, int inputX) {
if (inputY < 0 || inputX < 0 || inputY >= MapSize_Y || inputX >= MapSize_X) {
// 배열 밖이라면 No
return false;
} else if (isHoll()) {
// 구멍에 있다면 No
return false;
} else if (Main.Map[inputY][inputX] == 'O') {
// 구멍으로 간다면 Yes
return true;
}
// 빈칸이라면 Yes
return Main.Map[inputY][inputX] == '.';
}
public int getXY() {
return y * MapSize_X + x;
}
public boolean isHoll() {
return Ball.holeX == x && Ball.holeY == y;
}
}
public class Main {
private static boolean Debug = true;
private static final int left = 3, right = 1, up = 0, down = 2;
static int[] rotY = { -1, 0, 1, 0 };
static int[] rotX = { 0, 1, 0, -1 };
private static int MapSize_Y;
private static int MapSize_X;
static char[][] Map;
private static int minFindRed;
static Ball rBall;
private static Ball bBall;
private static int[][] Visited;
public static void main(String[] args) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "2048.txt");
FileReader reader = new FileReader(f);
br = new BufferedReader(reader);
} else {
br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용
}
StringTokenizer st;
// 맵 크기, 사과 개수
st = new StringTokenizer(br.readLine());
MapSize_Y = Integer.parseInt(st.nextToken());
MapSize_X = Integer.parseInt(st.nextToken());
Ball.MapSize_Y = MapSize_Y;
Ball.MapSize_X = MapSize_X;
// 맵 생성
Map = new char[MapSize_Y][];
for (int i = 0; i < MapSize_Y; i++) {
Map[i] = new char[MapSize_X];
String input = br.readLine();
char item;
for (int j = 0; j < MapSize_X; j++) {
// 맵에 기록, Ball 객체 생성
item = input.charAt(j);
switch (item) {
case 'B':
bBall = new Ball(i, j);
Map[i][j] = 'X';
break;
case 'R':
rBall = new Ball(i, j);
Map[i][j] = 'X';
break;
case 'O':
Ball.holeY = i;
Ball.holeX = j;
Map[i][j] = 'O';
break;
default:
Map[i][j] = item;
break;
}
}
}
// 방문배열 생성 [rBall.getXY()][bBall.getXY()]
int vSize = MapSize_X * MapSize_Y;
Visited = new int[vSize][];
for (int i = 0; i < vSize; i++) {
Visited[i] = new int[vSize];
}
minFindRed = Integer.MAX_VALUE;
// 프레임 체크 (첫 번째 순간은 중복되지 않는다.)
Visited[rBall.getXY()][bBall.getXY()] = 1;
// printMap();
tiltBoard(0);
// 시간 출력
System.out.println(minFindRed == Integer.MAX_VALUE ? -1 : minFindRed);
}
static Stack<Integer> debStack = new Stack();
private static void tiltBoard(int index) {
if (minFindRed <= index) {
// log("탐색불필요 " + debStack);
return;
} else if (bBall.isHoll()) {
// log("[블루볼] " + debStack);
return;
}
// 1.레드볼 여부 && 2. index == 10
if (rBall.isHoll()) { // && !bBall.isHoll() // 위에서 이미 체크
if (minFindRed > index) {
minFindRed = index;
}
// log("[레드볼]" + debStack.toString());
return;
} else if (index == 10) {
// log("[index 10] " + debStack);
return;
}
int redY = rBall.y;
int redX = rBall.x;
int blueY = bBall.y;
int blueX = bBall.x;
for (int i = 0; i < 4; i++) {
// 1. 공을 움직인다.
switch (i) {
case left:
if (redX < blueX) {
rBall.move(i);
bBall.move(i);
} else {
bBall.move(i);
rBall.move(i);
}
break;
case right:
if (redX > blueX) {
rBall.move(i);
bBall.move(i);
} else {
bBall.move(i);
rBall.move(i);
}
break;
case up:
if (redY < blueY) {
rBall.move(i);
bBall.move(i);
} else {
bBall.move(i);
rBall.move(i);
}
break;
case down:
if (redY > blueY) {
rBall.move(i);
bBall.move(i);
} else {
bBall.move(i);
rBall.move(i);
}
break;
}
// 2. 가능한 위치로 이동하여 탐색한다. (좌표 정보는 Ball 객체에 담겨있다.)
// 모두 제자리에 있으면, 탐색X
// 실행됬던 프레임이라면, 탐색X
if (rBall.x == redX && rBall.y == redY && bBall.x == blueX && bBall.y == blueY) {
// non-target
} else if (Visited[rBall.getXY()][bBall.getXY()] == 0) {
Visited[rBall.getXY()][bBall.getXY()] = 1;
// debStack.push(i);
// printMap();
tiltBoard(index + 1);
Visited[rBall.getXY()][bBall.getXY()] = 0;
// debStack.pop();
}
// 3. 공을 원위치로 시킨다.
rBall.move(redY, redX);
bBall.move(blueY, blueX);
}
}
// 디버깅용 프린트 맵
private static void printMap() {
for (int i = 0; i < MapSize_Y; i++) {
String temp = "";
for (int j = 0; j < MapSize_X; j++) {
temp += Map[i][j];
}
if (i == 0) {
temp += "시작";
}
log(temp);
}
}
public static void log(String input) {
if (Debug) {
System.out.println(input);
}
}
public static void log(String input, Object... args) {
if (Debug) {
System.out.println(String.format(input, args));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
백준 3671번: 산업 스파이의 편지 (0) | 2017.10.20 |
---|---|
백준 14500번: 테트로미노 (0) | 2017.10.20 |
백준 12100번: 2048(Easy) (0) | 2017.10.19 |
백준 3190번: 뱀 (0) | 2017.10.19 |
백준 14499번: 주사위 굴리기 (0) | 2017.10.19 |