BAEK_17836_공주님을구해라

05 Nov 2019 in Sidemenu / BaekJoon

https://www.acmicpc.net/problem/17836

17836. 공주님을 구해라

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	static int R, C, limit, count = 0, arriveCount = 0, gramCount = 0, ans = Integer.MAX_VALUE;
	static int[][] castle, pos = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static LinkedList<int[]> routeList = new LinkedList<int[]>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		R = toInt(st.nextToken());
		C = toInt(st.nextToken());
		limit = toInt(st.nextToken());
		castle = new int[R][C];
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < C; j++) {
				castle[i][j] = toInt(st.nextToken());
			}
		}
		System.out.println(moveToRescuePrincess() <= limit ? ans : "Fail");
	}

	static int moveToRescuePrincess() {
		moveToNextRoute(0, 0);
		while (!routeList.isEmpty()) {
			int size = routeList.size();
			for (int k = 0; k < size; k++) {
				int[] currentRoute = routeList.poll();
				int currentR = currentRoute[0];
				int currentC = currentRoute[1];
				checkAdjRoute(currentR, currentC);
			}
			count++;
		}
		return ans = arriveCount != 0 ? arriveAndGram() : notArriveAndGram();
	}

	static void checkAdjRoute(int r, int c) {
		for (int i = 0; i < 4; i++) {
			int nextR = r + pos[i][0];
			int nextC = c + pos[i][1];
			if (isNextRoute(nextR, nextC)) {
				arriveCount = arriveAtThePrincess(nextR, nextC) ? count + 1 : arriveCount;
				if (castle[nextR][nextC] == 2) {
					gramCount = count + getManhattanDistance(nextR, nextC) + 1;
					castle[nextR][nextC] = -1;
				} else {
					moveToNextRoute(nextR, nextC);
				}
			}
		}
	}

	static boolean isNextRoute(int r, int c) {
		return (r >= 0 && c >= 0 && r < R && c < C && Math.abs(castle[r][c]) != 1) ? true : false;
	}

	static boolean arriveAtThePrincess(int r, int c) {
		return (r == R - 1 && c == C - 1) ? true : false;
	}

	static int getManhattanDistance(int r, int c) {
		return R - r + C - c - 2;
	}

	static void moveToNextRoute(int r, int c) {
		routeList.offer(new int[] { r, c });
		castle[r][c] = -1;
	}

	static int arriveAndGram() {
		return gramCount != 0 ? Math.min(arriveCount, gramCount) : arriveCount;
	}

	static int notArriveAndGram() {
		return gramCount != 0 ? gramCount : ans;
	}

	static int toInt(String input) {
		return Integer.parseInt(input);
	}
}