import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Solution {
static boolean Debug = false;
private static int T;
private static int MapSize_Y;
private static int MapSize_X;
private static int FootSize;
private static int[][] Map; // 맵정보
private static int[][] Visited; // 시간정보
private static int[][] sTunnel; // 현재터널 방위측정
private static int[][] eTunnel; // 다음터널 방위측정
public static void main(String args[]) throws Exception {
BufferedReader br;
if (Debug) {
File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (11).txt");
FileReader reader = new FileReader(f);
br = new BufferedReader(reader);
} else {
br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용
}
StringTokenizer st;
eTunnel = new int[8][];
eTunnel[1] = new int[] { 1, 1, 1, 1 };
eTunnel[2] = new int[] { 1, 0, 1, 0 };
eTunnel[3] = new int[] { 0, 1, 0, 1 };
eTunnel[4] = new int[] { 0, 0, 1, 1 };
eTunnel[5] = new int[] { 1, 0, 0, 1 };
eTunnel[6] = new int[] { 1, 1, 0, 0 };
eTunnel[7] = new int[] { 0, 1, 1, 0 };
sTunnel = new int[8][];
sTunnel[1] = new int[] { 1, 1, 1, 1 };
sTunnel[2] = new int[] { 1, 0, 1, 0 };
sTunnel[3] = new int[] { 0, 1, 0, 1 };
sTunnel[4] = new int[] { 1, 1, 0, 0 };
sTunnel[5] = new int[] { 0, 1, 1, 0 };
sTunnel[6] = new int[] { 0, 0, 1, 1 };
sTunnel[7] = new int[] { 1, 0, 0, 1 };
int TestSize = Integer.parseInt(br.readLine());
for (T = 1; T <= TestSize; T++) {
st = new StringTokenizer(br.readLine());
MapSize_Y = Integer.parseInt(st.nextToken());
MapSize_X = Integer.parseInt(st.nextToken());
int doorY, doorX;
doorY = Integer.parseInt(st.nextToken());
doorX = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
Visited = new int[MapSize_Y][];
Map = new int[MapSize_Y][];
// Map 읽기
for (int i = 0; i < MapSize_Y; i++) {
Map[i] = new int[MapSize_X];
Visited[i] = new int[MapSize_X];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < MapSize_X; j++) {
Map[i][j] = Integer.parseInt(st.nextToken());
Visited[i][j] = -1;
}
}
findPath(doorY, doorX, time - 1);
FootSize = 0;
for (int i = 0; i < MapSize_Y; i++) {
for (int j = 0; j < MapSize_X; j++) {
if (Visited[i][j] != -1) {
FootSize++;
}
}
}
System.out.println(String.format("#%d %d", T, FootSize));
}
}
static int[] rotY = { -1, 0, 1, 0 };
static int[] rotX = { 0, 1, 0, -1 };
private static void findPath(int y, int x, int time) {
Visited[y][x] = time;
if (time == 0) {
// log(String.format("타임업 - 좌표(%d, %d) 시간: %d", y, x, time));
return;
}
// log(String.format("이동중 - 좌표(%d, %d) 시간: %d", y, x, time));
boolean isLast = true;
int nextY, nextX;
for (int i = 0; i < 4; i++) {
nextY = y + rotY[i];
nextX = x + rotX[i];
// 현재 터널에서 이동 가능한지 체크!
if (sTunnel[Map[y][x]][i] == 0) {
continue;
}
// 다음 경로에 진입할 수 있는지 체크!
if (isRight(nextY, nextX, i, time)) {
findPath(nextY, nextX, time - 1);
isLast = false;
}
}
}
public static boolean isRight(int y, int x, int rIndex, int time) {
if (x < 0 || x >= MapSize_X || y < 0 || y >= MapSize_Y) {
return false; // 배열 범위초과
} else if (Map[y][x] == 0) {
return false; // 벽
} else if (eTunnel[Map[y][x]][rIndex] == 0) {
return false; // 터널 이동 불가
} else if (Visited[y][x] > time) {
// 누군가가 방문했더라면, 나보다 먼저 방문했을 땐 못가고, 내가 더 먼저라면 갈 수 있다.
// 깊이 탐색이므로 시간 순으로 방문하지 않는다. 너비 탐색이라면 알아서 시간 순 탐색이니 신경쓰지 않아도 됨.
return false;
}
return true;
}
public static void log(String input) {
if (Debug) {
System.out.println(input);
}
}
public static void log(String input, Object... args) {
if (Debug) {
System.out.println(String.format(input, args));
}
}
}
'Knowledge > 알고리즘' 카테고리의 다른 글
백준 13458번: 시험 감독 (0) | 2017.10.17 |
---|---|
백준: 14503번: 로봇 청소기 (0) | 2017.10.17 |
2105. [모의 SW 역량테스트] 디저트 카페 (0) | 2017.10.15 |
2383. [모의 SW 역량테스트] 점심 식사시간 (0) | 2017.10.15 |
2477. [모의 SW 역량테스트] 차량 정비소 (0) | 2017.10.10 |