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));

}

}


}

+ Recent posts