Untitled

package day16_2006;

//import java.io.FileInputStream;
//import java.io.FileNotFoundException;
import java.util.Scanner;


class MyQueue{
	private int front, rear, max, cnt;
	private int[] q;
	
	public MyQueue(int a) {
		// TODO Auto-generated constructor stub
		front = 0;
		rear = -1;
		max = a;
		cnt = 0;
		q = new int[a];
	}
	
	public boolean isEmpty() {
		return cnt == 0;
	}
	
	public void enqueue(int a) {
		rear = (rear + 1) % max;
		q[rear] = a;
		cnt++;
	}
	
	public int dequeue() {
		int a = q[front];
		front = (front + 1) % max;
		cnt--;
		return a;
	}
}

public class hugo_v2 {
	
	static int row, col, hugox, hugoy, fi, li, oi, ans;
	static int[][] diamond, fire, lake, out, visit;
	static int[][] d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
	static MyQueue fqx, fqy;
	
	
	
	private static void bfsFire(){
		int r, c, dr, dc;
		while(!fqx.isEmpty()){
			r = fqx.dequeue(); c = fqy.dequeue();
			for(int i = 0; i < 4; i++){
				dr = r + d[0][i]; dc = c + d[1][i];
				if(dr >= 0 && dr < row && dc >= 0 && dc < col && fire[dr][dc] == -1 && lake[dr][dc] != 1){
					fire[dr][dc] = fire[r][c] + 1; 
					fqx.enqueue(dr); fqy.enqueue(dc);
				}
			}
		}
	}
	
	private static void backtrackHugo(int r, int c, int sum){
		
		if(out[r][c] == 1){
			if(ans < sum) ans = sum;
//			return;
		}
		
		int dr, dc;
		for(int i = 0; i < 4; i++){
			dr = r + d[0][i]; dc = c + d[1][i]; 
			if(dr >= 0 && dr < row && dc >= 0 && dc < col && visit[dr][dc] == -1){
				if(lake[dr][dc] == 1){
					 visit[dr][dc] = visit[r][c] + 2;
					 backtrackHugo(dr, dc, sum + diamond[dr][dc]);
					 visit[dr][dc] = -1;
				}
				else if(visit[r][c] + 1 < fire[dr][dc] ||fire[dr][dc] == -1){
					visit[dr][dc] = visit[r][c] + 1;
					backtrackHugo(dr, dc, sum + diamond[dr][dc]);
					visit[dr][dc] = -1;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		try {
//			System.setIn(new FileInputStream("D:\\Trainee\\SRV_training\\src\\day16_2006\\hugo.txt"));
//		} catch (FileNotFoundException e) {
//			// TODO Auto-generated catch block
//			e.printStackTrace();
//		}
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			row = sc.nextInt(); col = sc.nextInt();
			hugox = sc.nextInt() - 1; hugoy = sc.nextInt() - 1;
			int a, b;
			fi = sc.nextInt();
			
			diamond = new int[row][col];
			fire = new int[row][col];
			lake = new int[row][col];
			out = new int[row][col];
			visit = new int[row][col];
			fqx = new MyQueue(row * col);
			fqy = new MyQueue(row * col);
			
			
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					fire[i][j] = -1;
					visit[i][j] = -1;
				}
			}
			visit[hugox][hugoy] = 0;
			
			for(int i = 0; i < fi; i++){
				a = sc.nextInt() - 1; b = sc.nextInt() - 1;
				fire[a][b] = 0;
				fqx.enqueue(a); fqy.enqueue(b);
			}
			
			li = sc.nextInt();
			for(int i = 0; i < li; i++){
				a = sc.nextInt() - 1; b = sc.nextInt() - 1;
				lake[a][b] = 1;
			}
			
			oi = sc.nextInt();
			for(int i = 0; i < oi; i++){
				a = sc.nextInt() - 1; b = sc.nextInt() - 1;
				out[a][b] = 1;
			}
			
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					diamond[i][j] = sc.nextInt();
				}
			}
			
			bfsFire();
			ans = -1;
			backtrackHugo(hugox, hugoy, diamond[hugox][hugoy]);
			System.out.println("Case #" + tc);
			System.out.println(ans);
			
		}
	}
}