BAEK_17836_공주님을구해라

11월 15일 in Category / Algorithm

BAEKJOON

17836. 공주님을구해라

fail은 Fail이 아닙니다.

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

public class Main {
	static int N, M, map[][], T, COUNT;
	static int dir[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
	static boolean visited[][][];

	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(in.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());

		map = new int[N + 1][M + 1];
		visited = new boolean[N + 1][M + 1][2];
		COUNT = T + 1;

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 1; j <= M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		bfs();

		System.out.println(COUNT > T ? "Fail" : COUNT);
	}

	private static void bfs() {
		Queue<Integer> q = new LinkedList<Integer>();

		q.offer(1);
		q.offer(1);
		q.offer(0);

		visited[1][1][0] = true;

		int r, c, sword, dr, dc, count = 0;

		while (!q.isEmpty() || count <= T) {

			for (int i = 0, size = q.size() / 3; i < size; i++) {
				r = q.poll();
				c = q.poll();
				sword = q.poll();
				if (isPrincess(r, c)) {
					COUNT = count;
					return;
				}
				for (int d = 0; d < 4; d++) {
					dr = r + dir[d][0];
					dc = c + dir[d][1];
					if (check(dr, dc)) {
						if (sword == 2) {
							if (!visited[dr][dc][1]) {
								visited[dr][dc][0] = true;
								visited[dr][dc][1] = true;
								q.offer(dr);
								q.offer(dc);
								q.offer(sword);
							}
						} else {
							if (!visited[dr][dc][0] && map[dr][dc] != 1) {
								visited[dr][dc][0] = true;
								q.offer(dr);
								q.offer(dc);
								q.offer(map[dr][dc]);
							}
						}
					}
				}
			}
			count++;
		}
	}

	private static boolean check(int r, int c) {
		if (r == 0 || c == 0 || r == N + 1 || c == M + 1)
			return false;
		return true;
	}

	private static boolean isPrincess(int r, int c) {
		if (r == N && c == M)
			return true;
		return false;
	}

}