[Swea - 1953] 탈주범 검거

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpLlKAQ4DFAUq

SW Expert Academy

 

1. 유형

시뮬레이션

 

2. 풀이

현제 파이프가 위로 뚫려 있다면 다음 좌표의 파이프가 아래로 뚫려 있어야 한다.

 

3. 코드

package swea;

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

public class Swea_1953탈주법_검거 {
	static int dr[] = { -1, 1, 0, 0 };// 상하
	static int dc[] = { 0, 0, -1, 1 };// 좌우
	static int N, M, R, C, L, map[][], ans = 1;

	static class Pair {
		int r, c, d;

		public Pair(int r, int c, int d) {
			// TODO Auto-generated constructor stub
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.valueOf(in.readLine());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.readLine(), " ");
			N = Integer.valueOf(st.nextToken());
			M = Integer.valueOf(st.nextToken());
			R = Integer.valueOf(st.nextToken());
			C = Integer.valueOf(st.nextToken());
			L = Integer.valueOf(st.nextToken());
			map = new int[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < M; j++) {
					map[i][j] = Integer.valueOf(st.nextToken());
				}
			}
			ans=1;
			bfs();
			System.out.println("#"+tc+" "+ans);
		}
	}
	static boolean visited[][];
	static Queue<Pair> q;
	static void bfs() {
		q = new LinkedList<>();
		q.add(new Pair(R, C, 1));
		visited = new boolean[N][M];
		visited[R][C] = true;
		while (!q.isEmpty()) {
			Pair cur = q.poll();
			for(int k=0; k<4; k++) {
				int nr = cur.r + dr[k];
				int nc = cur.c + dc[k];
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if(visited[nr][nc] || map[nr][nc] == 0) continue;
				if(cur.d+1>L) continue;
				int type = map[cur.r][cur.c];
				int next = map[nr][nc];
				switch (k) {
				case 0:
					if(type == 1 || type == 2 || type == 4 || type == 7) {
						if(next == 1 || next == 2 || next == 5 || next == 6) {
							visited[nr][nc] = true;
							q.offer(new Pair(nr, nc, cur.d+1));
							ans++;
						}
					}
					break;
				case 1:
					if(type == 1 || type == 2 || type == 5 || type == 6) {
						if(next == 1 || next == 2 || next == 4 || next == 7) {
							visited[nr][nc] = true;
							q.offer(new Pair(nr, nc, cur.d+1));
							ans++;
						}
					}
					break;
				case 2:				
					if(type == 1 || type == 3 || type == 6 || type == 7) {
						if(next == 1 || next == 3 || next == 4 || next == 5) {
							visited[nr][nc] = true;
							q.offer(new Pair(nr, nc, cur.d+1));
							ans++;
						}
					}
					break;
				case 3:
					if(type == 1 || type == 3 || type == 4 || type == 5) {
						if(next == 1 || next == 3 || next == 6 || next == 7) {
							visited[nr][nc] = true;
							q.offer(new Pair(nr, nc, cur.d+1));
							ans++;
						}
					}
					break;
				default:
					break;
				}
			}
		}
	}

}