[BAEK] 17836. 공주님을 구해라!

11월 15일 in Category / ProblemSolving

[BaekJoon] 17836번 공주님을 구해라!

17836. 공주님을 구해라!

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,T;
	static int[][] map;
	static boolean[][][] visited;
	static int[][] dir = { {-1,0},{1,0},{0,-1},{0,1} };
	static int gramy,gramx;
	static Queue<int[]> queue;
	static int answer;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		
		map = new int[N+1][M+1];
		for(int i=1;i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<=M;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		queue = new LinkedList<>();
		queue.offer(new int[]{1,1,0,0});
		visited = new boolean[N+1][M+1][2];
		visited[1][1][0]=true;
		answer = Integer.MAX_VALUE>>2;
		moveSoldier();
		
		if(answer == Integer.MAX_VALUE>>2) System.out.println("Fail");
		else System.out.println(answer);
	}
	
	public static void moveSoldier() {
		
		while(!queue.isEmpty()) {
			int[] solider = queue.poll();
			int soldierY = solider[0];
			int soldierX = solider[1];
			int soldierD = solider[2];
			int soliderG = solider[3];
			
			if(soldierD>T) return;
			
			if(soldierY == N && soldierX == M) {
				if(answer>soldierD) answer = soldierD;
			}
			
			for(int i=0;i<dir.length;i++) {
				int dr = soldierY+dir[i][0];
				int dc = soldierX+dir[i][1];
				
				if(dr>=1 && dc>=1 && dr<=N && dc<=M 
						&& soldierD+1<=T
						&& !visited[dr][dc][soliderG]) {
					
					switch(map[dr][dc]) {
					case 0:
						queue.offer(new int[] {dr,dc,soldierD+1,soliderG});
						break;
					case 1:
						if(soliderG==1) queue.offer(new int[] {dr,dc,soldierD+1,soliderG});
						else continue;
						break;
					case 2:
						queue.offer(new int[] {dr,dc,soldierD+1,1});
						break;
					}
					visited[dr][dc][soliderG]=true;
				}
			}
		}
	}
}