• Depth L만큼 bfs 수행
  • 시작 위치부터 시간이 1로 계산되어야 하기 때문에 cnt가 1부터 시작
  • 현재의 type과 다음 터널의 type의 조합에 따라 이동 가능 여부를 확인해야 한다
  • 반대 방향의 index 값이 2 차이 나도록 설정한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73



import java.io.*;
import java.util.*;

public class Solution {
	static int N, M, L;
	static int[] dx = {-1, 0, 1,  0};
	static int[] dy = { 0, 1, 0, -1};
	static int[][] board;
	static boolean[][] visited;
	static int[][] dirs = new int[8][];
	static {
		dirs[1] = new int[]{0, 1, 2, 3}; dirs[2] = new int[]{0, 2};
		dirs[3] = new int[]{1, 3}; dirs[4] = new int[]{0, 1};
		dirs[5] = new int[]{1, 2}; dirs[6] = new int[]{2, 3};
		dirs[7] = new int[]{3, 0};
	}

	static int bfs(int sr, int sc) {
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(sr); q.offer(sc);
		visited[sr][sc] = true;

		int cnt = 1, res = 1;
		while (!q.isEmpty() && cnt < L) {
			for (int qs = 0, qSize = q.size()/2; qs < qSize; qs++) {
				int r = q.poll();
				int c = q.poll();
				int type = board[r][c];
				for (int dir : dirs[type]) {
					int nr = r + dx[dir];
					int nc = c + dy[dir];
					if \(nr < 0 \|| nr >= N \|| nc < 0 \|| nc >= M 
							\|| board\[nr]\[nc] == 0 \|| visited\[nr]\[nc]) 
						continue;

					int ntype = board[nr][nc];
					for (int ndir : dirs[ntype]) {
						if (ndir != (dir + 2) % 4) continue;

						visited[nr][nc] = true;
						res++;
						q.offer(nr); q.offer(nc);
						break;
					}
				}
			}
			cnt++;
		}
		return res;
	}

	public static void main(String[] args) throws  Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int testcase = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= testcase; tc++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			int sr = Integer.parseInt(st.nextToken());
			int sc = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());

			board = new int[N][M];
			visited = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine());
				for (int j = 0; j < M; j++)
					board[i][j] = Integer.parseInt(st.nextToken());
			}
			System.out.println("#" + tc + " " + bfs(sr, sc));
		}
	}
}