Untitled

#include <iostream>
using namespace std;
class Queue
{
private:
	int Data[300];
public:
	int front, rear;
	Queue();
	void enQueue(int value);
	void reset();
	int deQueue();
	bool is_Empty();
};
Queue::Queue(){
	front=rear=-1;
}
void Queue::reset(){
	front=rear=-1;
}
void Queue::enQueue(int value){
	Data[++rear]=value;
}
int Queue::deQueue(){
	return Data[++front];
}
bool Queue::is_Empty(){
	return front==rear;
}

Queue rFQueue, cFQueue;
int N,M,K,SR,SC, Max, cntD, nextStep;
int D[15][15], Lake[15][15], Exit[15][15],
	visitF[15][15], visitH[15][15];
int cntFire, cntLake, cntExit;
int dx[]={0,0,-1,1},
	dy[]={-1,1,0,0};
int nr, nc, cr, cc;

void EtFire(){
	while (rFQueue.is_Empty()==false){
		cr=rFQueue.deQueue();
		cc=cFQueue.deQueue();
		for (int idx=0; idx<4; idx++){
			nr=cr+dx[idx];
			nc=cc+dy[idx];
			if (nr>=0 && nr<N && nc>=0 && nc<M &&
				visitF[nr][nc]==1000000 && Lake[nr][nc]==0)
			{
				rFQueue.enQueue(nr);
				cFQueue.enQueue(nc);
				visitF[nr][nc]=visitF[cr][cc]+1;
			}
		}
	}

}

void backtrack(int r, int c, int cntStep){
	if (Exit[r][c]==1){
		if (Max<cntD)
			Max=cntD;
	}
	for (int i=0; i<4; i++){
		int Nr = r+dx[i];
		int Nc = c+dy[i];
		if (Nr>=0 && Nr<N && Nc>=0 && Nc<M && visitH[Nr][Nc]==false)
		{
			if (Lake[Nr][Nc]==0){
				nextStep=cntStep+1;
				if (nextStep<visitF[Nr][Nc])
				{
					cntD += D[Nr][Nc];
					visitH[Nr][Nc]=true;
					backtrack(Nr,Nc,nextStep);
					cntD -= D[Nr][Nc];
					visitH[Nr][Nc]=false;
				}
			}
			else {
				nextStep=cntStep+2;
				cntD += D[Nr][Nc];
				visitH[Nr][Nc]=true;
				backtrack(Nr,Nc,nextStep);
				cntD -= D[Nr][Nc];
				visitH[Nr][Nc]=false;
			}
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int T, x, y ;
	cin>>T;
	for (int tc=1; tc<=T; tc++){
		rFQueue.reset();
		cFQueue.reset();

		cin>>N>>M>>SR>>SC;
		SR--;
		SC--;

		for (int i=0; i<N; i++){
			for (int j=0; j<M; j++){
				Lake[i][j]=0;
				Exit[i][j]=0;
				visitF[i][j]=1000000;
				visitH[i][j]=0;
			}
		}
		visitH[SR][SC]=1;

		cin>>cntFire;
		for (int i=0; i<cntFire; i++){
			cin>>x;
			cin>>y;
			visitF[x-1][y-1]=0;
			rFQueue.enQueue(x-1);
			cFQueue.enQueue(y-1);
		}

		cin>>cntLake;
		for (int i=0; i<cntLake; i++){
			cin>>x;
			cin>>y;
			Lake[x-1][y-1]=1;
		}

		cin>>cntExit;
		for (int i=0; i<cntExit; i++){
			cin>>x;
			cin>>y;
			Exit[x-1][y-1]=1;
		}

		for (int i=0; i<N; i++){
			for (int j=0; j<M; j++){
				cin>>D[i][j];
			}
		}

		EtFire();
		cntD=D[SR][SC];
		Max=-1;
		backtrack(SR,SC,0);
		cout<<"Case #"<<tc<<endl<<Max<<endl;
	}

	return 0;
}