Untitled

#include <iostream>
using namespace std;

#define MAX_Q 400

class Queue{
public:
	int data[MAX_Q];
	int front, rear;

	Queue();
	void reset();
	void enQueue(int input);
	int deQueue();
	bool isEmpty();
};

Queue::Queue(){
	front = rear = -1;
}

void Queue::reset(){
	front = rear = -1;
}

void Queue::enQueue(int input){
	data[++rear]=input;
}

int Queue::deQueue(){
	return data[++front];
}

bool Queue::isEmpty(){
	return (front==rear);
}

Queue rQ, cQ;

int T, tc;
int N, M, SR, SC;
int K, ki, kj;
int map[20][20];
int visit[20][20];
int fire_time[20][20];
int diamond[20][20];
int exits[60][2];
int exit_len;
int spinR[4]={0,1,0,-1};
int spinC[4]={1,0,-1,0};
int max_diam;
int can_exit;
int max_ftime;
int exit_map[20][20];

void clr_ftime(){
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			fire_time[i][j]=-1;
		}
	}
}

void clr_map(){
	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			map[i][j]=0;
			visit[i][j]=0;
			exit_map[i][j]=0;
		}
	}
}

void bfs()
{
	rQ.reset();
	cQ.reset();
	clr_ftime();

	for(int i=1; i<=N; i++){
		for(int j=1; j<=M; j++){
			if(map[i][j]==2){
				rQ.enQueue(i);
				cQ.enQueue(j);
				fire_time[i][j]=0;
			}
		}
	}
	while(rQ.isEmpty()==false)
	{
		int cR = rQ.deQueue();
		int cC = cQ.deQueue();
		for(int k=0; k<4; k++){
			int nR = cR + spinR[k];
			int nC = cC + spinC[k];
			if(nR>=1 && nR<=N && nC>=1 && nC<=M){
				if(map[nR][nC]!=3 && fire_time[nR][nC]==-1){
					rQ.enQueue(nR);
					cQ.enQueue(nC);
					fire_time[nR][nC]=fire_time[cR][cC]+1;
				}
			}
		}
	}
}

int isExit(int row, int col){
	for(int i=0; i<exit_len; i++){
		if(exits[i][0]==row && exits[i][1]==col){
			return 1;
		}
	}
	return 0;
}

void backtrack(int row, int col, int p_time, int p_diam)
{
	if(p_time>=fire_time[row][col] && fire_time[row][col]!=-1){
		return;
	}
	if(max_ftime!=-1 && p_time>=max_ftime){
		return;
	}
	for(int i=0; i<4; i++)
	{
		int nR = row + spinR[i];
		int nC = col + spinC[i];
		if(nR>=1 && nR<=N && nC>=1 && nC<=M)
		{
			if(visit[nR][nC]==0)
			{
				visit[nR][nC]=1;
				if(map[row][col]==0){
					backtrack(nR, nC, p_time+1, p_diam+diamond[row][col]);
				} else if(map[row][col]==3){
					backtrack(nR, nC, p_time+2, p_diam+diamond[row][col]);
				}
				visit[nR][nC]=0;
			}
		}
	}
	if(exit_map[row][col]){
		can_exit=1;
		max_diam = (max_diam > (p_diam+diamond[row][col]))? max_diam : (p_diam+diamond[row][col]);
		return;
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(tc=1; tc<=T; tc++)
	{
		cin >> N >> M >> SR >> SC; //Hugo
		clr_map();
		exit_len=0;
		cin >> K;
		for(int i=0; i<K; i++){
			cin >> ki;
			cin >> kj;
			map[ki][kj]=2; //Fire
		}
		cin >> K;
		for(int i=0; i<K; i++){
			cin >> ki;
			cin >> kj;
			map[ki][kj]=3; //Water
		}
		cin >> K;
		for(int i=0; i<K; i++){
			cin >> ki;
			cin >> kj;
			exits[exit_len][0]=ki;
			exits[exit_len][1]=kj;
			exit_len++;
			exit_map[ki][kj]=1; //Exit
		}
		//Diamond
		for(int i=1; i<=N; i++){
			for(int j=1; j<=M; j++){
				cin >> diamond[i][j];
			}
		}
		//Solve
		max_diam = 0;
		can_exit = 0;
		//Create fire time table
		bfs();
		//Find max fire time
		max_ftime=0;
		for(int i=0; i<exit_len; i++){
			if(fire_time[exits[i][0]][exits[i][1]]==-1){
				max_ftime=-1;
				break;
			}
			max_ftime = (max_ftime > fire_time[exits[i][0]][exits[i][1]])? max_ftime : fire_time[exits[i][0]][exits[i][1]];
		}
		//Backtrack
		visit[SR][SC]=1;
		backtrack(SR, SC, 0, 0);
		visit[SR][SC]=0;
		//Print
		cout << "Case #" << tc << endl;
		if(can_exit==1){
			cout << max_diam << endl;
		} else {
			cout << -1 << endl;
		}
	}
	return 0;
}