Untitled

#include<iostream>
using namespace std;

int T, hang, cot, vtdx, vtdy;
int time[5][5], visit[5][5], diamond[5][5], fire_lake[5][5], out[5][5];
int front, rear;
int n, x, y;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int flag = 0, n_out, count1, rs;

struct toado{
	int x;
	int y;
};
toado queue[10000000];
void init() {
	front = 0;
	rear = 0;
}
void push(int x, int y) {
	queue[rear].x = x;
	queue[rear].y = y;
	rear ++;
}
toado pop() {
	toado t = queue[front];
	front ++;
	return t;
}

void bfs() {
	init();
	for(int i = 0; i < hang; i ++) {
		for(int j = 0; j < cot; j ++) {
			if(!fire_lake[i][j]) {
				push(i, j);
				visit[i][j] = 1;
			}
		}
	}
	while(front < rear) {
		toado t = pop();
		for(int i = 0; i < 4; i ++) {
			int xn = t.x + dx[i];
			int yn = t.y + dy[i];
			if(xn >= 0 && xn < hang && yn >= 0 && yn < cot && fire_lake[xn][yn] != 100000 && visit[xn][yn]==0) {
				push(xn, yn);
				fire_lake[xn][yn] = fire_lake[t.x][t.y] + 1;
				visit[xn][yn] = 1;
			}
		}
	}
}

void dequy(int x, int y, int check, int count1) {
	flag = 0;
	for(int i = 0; i < n_out; i ++) {
		if(x == out[i][0] && y == out[i][1]) {
			if(rs < count1) rs = count1;
			flag = 1;
		}
	}
	cout << x << " " << y << endl;;
	if(flag) return;

	for(int i = 0; i < 4; i ++) {
		int xn = x + dx[i];
		int yn = y + dy[i];
		if (xn >= 0 && xn < hang && yn >= 0 && yn < cot && visit[xn][yn] == 0) {
			if(fire_lake[xn][yn] != 100000 && check +1 < fire_lake[xn][yn]) {
				visit[xn][yn] = 1;
				dequy(xn, yn, check + 1, count1 + diamond[xn][yn]);
				visit[xn][yn] = 0;
			}
			else if(fire_lake[xn][yn] == 100000) {
				visit[xn][yn] = 1;
				dequy(xn, yn, check + 2, count1 + diamond[xn][yn]);
				visit[xn][yn] = 0;
			}
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin >> T;
	for(int test_case = 1; test_case <= T; test_case ++) {
		cin >> hang >> cot;
		cin >> vtdx >> vtdy;
		vtdy --; vtdx --;
		for(int i = 0; i < hang; i ++) {
			for(int j = 0; j < cot; j ++) {
				visit[i][j] = 0;
				diamond[i][j] = 0;
				fire_lake[i][j] = 10000;
				out[i][j] = 0;
			}
		}
		//chay
		cin >> n;
		for(int i = 0; i < n; i ++) {
			cin >> x >> y;
			fire_lake[x-1][y-1] = 0;
		}
		//ho
		cin >> n;
		for(int i = 0; i < n; i ++) {
			cin >> x >> y;
			fire_lake[x-1][y-1] = 100000;
		}
		//thoat
		cin >> n_out;
		for(int i = 0; i < n; i ++) {
			cin >> x >> y;
			out[x-1][y-1] = 1;
		}
		//kc
		for(int i = 0; i < hang; i ++) {
			for(int j = 0; j < cot; j ++) {
				cin >> diamond[i][j];
			}
		}

		rs = 0; count1 = 0;
		bfs();
		for(int i = 0; i < hang; i ++) {
			for(int j = 0; j < cot; j ++) {
				visit[i][j] = 0;
				cout << fire_lake[i][j] << "\t";
			}
			cout << endl;
		}
		visit[vtdx][vtdy] = 1;
		dequy(vtdx, vtdy, 0, diamond[vtdx][vtdy]);
		
		cout << "Case #" << test_case << endl << rs << endl;
	}
	return 0;
}