[SWEA] 탈주범 검거

package com.study.classAlgo;

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

public class SWEA_1953_탈주범_검거 {
	//1. t번 반복, t케이스
	//2. n:row, m : column, r,c, l:탈출 후 소요된 시간
	//3. 갈 수 있는 장소인지 판별해야 한다.
	//3-1. 0 : 터널이 없는 장소 -> 만나면 어차피 못감
	//3-2. 1~7 :  터널들을 7개, 각각 boolean[4]
	//3-3. 만약 현재 터널 current와 current+1의 boolean이 같으면 이어지고 아니면 안이어진다.
	
	static int tc,N,M,r,c,l,count;
	static int[][] map;
	static boolean[][] isVisited;
	//상하좌우
	static boolean[][] pipes = {{false,false,false,false},{true,true,true,true},{true,true,false,false},{false,false,true,true}
	,{true,false,false,true},{false,true,false,true},{false,true,true,false},{true,false,true,false}};
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static Queue<Node> queue;
	static class Node {
		int x;
		int y;
		int level;
		
		public Node(int x, int y,int level) {
			super();
			this.x = x;
			this.y = y;
			this.level = level;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		tc = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=tc; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			l = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			isVisited = new boolean[N][M];
			count = 0;
			queue = new LinkedList<Node>();
			
			for (int i = 0; i < N; i++) {//map생성
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			queue.add(new Node(r,c,1));
			isVisited[r][c] = true;
			solve();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(isVisited[i][j]) count++;
				}
			}
			
			System.out.println("#"+t+" "+count);
		}
	}
	
	
	private static void solve() {
		int timer = 0;
		while(!queue.isEmpty()) {
			Node n = queue.poll();
			int x = n.x;
			int y = n.y;
			int level = n.level;
			if(level >= l) return;
			for(int i=0; i<4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				
				if(isValid(nx,ny)&&map[nx][ny]!=0) {
					if( !isVisited[nx][ny]) {
						if(isPossible(x,y,nx,ny,i,nextDirection(i))) {
							isVisited[nx][ny] = true;
							queue.offer(new Node(nx,ny,level+1));
							timer=level+1;
							
						}
					}
				}
			}		
		}
	}
	
	private static int nextDirection(int direction) {
		int nextDirection= 0;
		if(direction == 0) {
			nextDirection = 1;
		}else if(direction == 1) {
			nextDirection = 0;
		}else if(direction == 2) {
			nextDirection = 3;
		}else if(direction == 3) {
			nextDirection = 2;
		}
		return nextDirection;
	}

	private static boolean isPossible(int x, int y, int nx, int ny,int direction,int nextDirection) {
		//map[x][y] 현재 파이프 종류
		//map[nx][ny] 지나가려고 하는 파이프 종류
		//3-3. 만약 현재 터널 current와 current+1의 boolean이 같으면 이어지고 아니면 안이어진다.
		
		int currentPipe = map[x][y];
		int nextPipe = map[nx][ny];
		return pipes[currentPipe][direction] && pipes[nextPipe][nextDirection];
	}


	private static boolean isValid(int nx, int ny) {
		return (nx>=0 && nx<N && ny>=0 && ny<M) ? true : false;
	}

}