pipe network

package day16_2006;

import java.util.Scanner;

public class pipe_network {
	
	static int[][] ngang = {{1, 0, 1, 1, 1, 0, 0},
						   {0, 0, 0, 0, 0, 0, 0},
						   {1, 0, 1, 1, 1, 0, 0},
						   {0, 0, 0, 0, 0, 0, 0},
						   {0, 0, 0, 0, 0, 0, 0},
						   {1, 0, 1, 1, 1, 0, 0},
						   {1, 0, 1, 1, 1, 0, 0}},
				   doc = {{1, 1, 0, 0, 1, 1, 0},
						 {1, 1, 0, 0, 1, 1, 0},
						 {0, 0, 0, 0, 0, 0, 0},
						 {1, 1, 0, 0, 1, 1, 0},
						 {0, 0, 0, 0, 0, 0, 0},
						 {0, 0, 0, 0, 0, 0, 0},
						 {1, 1, 0, 0, 1, 1, 0}};
	static int row, col, sx, sy, limit, ans;
	static int startx, starty, endx, endy;
	static int[][] visit;
	static int[][] map;
	
	private static void BFS(){
		MyQueue qx = new MyQueue(row * col);
		MyQueue qy = new MyQueue(row * col);
		qx.enqueue(sx); qy.enqueue(sy);
		
		int x, y, dx, dy, val1, val2;
		
		while(!qx.isEmpty()){
			x = qx.dequeue(); y = qy.dequeue();
			val1 = map[x][y];
			
			if(visit[x][y] < limit){
				//up
				dx = x - 1; dy = y;
				if(dx >= 0 && visit[dx][dy] == 0){
					val2 = map[dx][dy];
					if(doc[val1][val2] == 1){
						visit[dx][dy] = visit[x][y] + 1;
						ans++;
						qx.enqueue(dx); qy.enqueue(dy);
					}
				}
				
				//right
				dx = x; dy = y + 1;
				if(dy < col && visit[dx][dy] == 0){
					val2 = map[dx][dy];
					if(ngang[val2][val1] == 1){
						visit[dx][dy] = visit[x][y] + 1;
						ans++;
						qx.enqueue(dx); qy.enqueue(dy);
					}
				}
				
				//down
				dx = x + 1; dy = y;
				if(dx <= endx && visit[dx][dy] == 0){
					val2 = map[dx][dy];
					if(doc[val2][val1] == 1){
						visit[dx][dy] = visit[x][y] + 1;
						ans++;
						qx.enqueue(dx); qy.enqueue(dy);
					}
				}
				
				//left
				dx = x; dy = y - 1;
				if(dy >= starty && visit[dx][dy] == 0){
					val2 = map[dx][dy];
					if(ngang[val1][val2] == 1){
						visit[dx][dy] = visit[x][y] + 1;
						ans++;
						qx.enqueue(dx); qy.enqueue(dy);
					}
				}
				
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			row = sc.nextInt(); col = sc.nextInt();
			sx = sc.nextInt(); sy = sc.nextInt();
			limit = sc.nextInt();

			visit = new int[row][col];
			visit[sx][sy] = 1;
			map = new int[row][col];
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					map[i][j] = sc.nextInt() - 1;
					if(map[i][j] == -1) visit[i][j] = -1;
				}
			}
			
			
			startx = sx - limit > 0 ? sx - limit : 0;
			endx = sx + limit < row ? sx + limit : row - 1;
			starty = sy - limit > 0 ? sy - limit : 0;
			endy = sx + limit < col ? sy + limit : col - 1;
			
			ans = 1;
			BFS();
			System.out.println("Case #" + tc + " " + ans);
			
		}
	}
}