Untitled

#include <iostream>
using namespace std;

#define MAX_SIZE 10000000
int front = -1;
int rear = -1;
int Arx[MAX_SIZE];
int Ary[MAX_SIZE];
int Index[MAX_SIZE];

class queue {
public:
	bool isEmpty();
	void enqueue(int arx, int ary, int index);
	void dequeue();
	void peek(int &arx, int &ary, int &index);
};

bool queue :: isEmpty()
{
	if(front == rear)
	{
		return true;
	}
	return false;
}

void queue :: enqueue(int arx, int ary, int index)
{
	front++;
	Arx[front] = arx;
	Ary[front] = ary;
	Index[front] = index;
}

void queue :: dequeue()
{
	rear++;
}

void queue :: peek(int &arx, int &ary, int &index)
{
	arx = Arx[rear + 1];
	ary = Ary[rear + 1];
	index = Index[rear + 1];
}

int M, N, xbgin, ybgin;
int arFire[6][17];
int arRive[6][17];
int arr[6][17];
int arExit[6][17];
int arKc[6][17];

void reset()
{
	for(int i = 0; i < 6; i++)
	{
		for(int j = 0;j < 17; j++)
		{
			arFire[i][j] = -1;
			arRive[i][j] = 0;
			arr[i][j] = 0;
			arKc[i][j] = 0;
			arExit[i][j] = 0;
		}
	}
}

int dx[] = { -1,  0,  0,  1};
int dy[] = {  0,  1, -1,  0};


// BFS dung de lan lua
void BFS(int x1, int y1)
{
	int index = 0;
	queue qe;
	qe.enqueue(x1, y1, index);
	arFire[x1][y1] = index;
	while(!qe.isEmpty())
	{
		int x, y;
		qe.peek(x, y, index);
		qe.dequeue();
		for(int i = 0; i < 4; i++)
		{
			int t = x + dx[i];
			int k = y + dy[i];
			if(t >= 1 && t <= N && k >= 1 && k <= M)
			{
				if(arFire[t][k] == -1 && arRive[t][k] != 1)
				{
					qe.enqueue(t, k, index + 1);
					arFire[t][k] = index + 1;
				}
				else if(arFire[t][k] > index + 1 && arRive[t][k] != 1)
				{
					qe.enqueue(t, k, index + 1);
					arFire[t][k] = index + 1;
				}
			}
		}
	}
}


// goi backtrack de xem duong an duoc nhieu kim cuong nhat
void hugo(int &max, int kc, int x, int y, int time)
{
	if(arFire[x][y] <= time && arFire[x][y] != -1)
	{
		return;
	}
	if(arExit[x][y] == 1)
	{
		if(max < kc)
		{
			max = kc;
		}
	}
	for(int i = 0; i < 4; i++)
	{
		int t = x + dx[i];
		int k = y + dy[i];
		if(t >= 1 && t <= N && k >= 1 && k <= M)
		{
			int nexttime;
			if(arRive[t][k] == 1)
	        {
		        nexttime = time + 2;
	        }
	        else
	        {
		        nexttime = time + 1;
	         }
			if(((arFire[t][k] == -1) || (arFire[t][k] > nexttime)) && arr[t][k] == 0)
			{
				arr[t][k] = -1;
				hugo(max , kc + arKc[t][k], t, k, nexttime);
				arr[t][k] = 0;
			}

		}
	}
}


int main()
{
	freopen("input.txt", "r", stdin);
	int testcase;
	cin >> testcase;
	for(int tc = 1; tc <= testcase; tc++)
	{
		reset();
		front = rear = -1;
		cin >> N >> M >> xbgin >> ybgin;
		int fire;
		// gan gia tri ban dau cua ngon lua
		// bfs xem ngon lua co the lan den dau
		cin >> fire;
		for(int i = 0; i < fire; i++)
		{
			int x, y;
			cin >> x >> y;
			arFire[x][y] = 0;
		}
		// khu vuc ho nuoc 
		int ho;
		cin >> ho;
		for(int i = 0; i < ho; i++)
		{
			int x, y;
			cin >> x >> y;
			arRive[x][y] = 1;
		}
		// khu vuc thoat hiem
		int exit;
		cin >> exit;
		for(int i = 0; i < exit; i++)
		{
			int x, y;
			cin >> x >> y;
			arExit[x][y] = 1; // cho thoat hiem
		}
		// vi tri co kim cuong
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= M; j++)
			{
				cin >> arKc[i][j];
			}
		}
		// BFS de lan lua
		for(int i = 1; i <= N; i++)
		{
			for(int j = 1; j <= M; j++)
			{
				if(arFire[i][j] == 0)
				{
					BFS(i, j);
				}
			}
		}
		int max = 0;
		arr[xbgin][ybgin] = -1;
		hugo(max , arKc[xbgin][ybgin], xbgin, ybgin, 0);
		if(max != 0)
		{
		    cout<<"Case #"<<tc<<endl<<max<<endl;
		}
		else
		{
			cout<<"Case #"<<tc<<endl<<-1<<endl;
		}
	}
}