Untitled

#include <iostream>
using namespace std;

int N, M;
int x_start, y_start;
int numFires, numLakes, numGates;
int map[20][20];
int fires[20][20];
int diamonds[20][20];
int visited[20][20];
int vs[20][20];
int dx[] = {-1, 0,  0, 1};
int dy[] = { 0, 1, -1, 0};
int fires_index[20][2];
int ans;

// Queue
int qx[1000000];
int qy[1000000];
int front;
int rear;
bool isEmpty(){
	return front == -1;
}
void push(int x, int y){
	if(front == -1) front = 0;
	rear++;
	qx[rear] = x;
	qy[rear] = y;
}
void pop(){
	if(front >= rear) front = rear = -1;
	else front++;
}

// Reset
void reset(){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			diamonds[i][j] = 0;
			fires[i][j] = 0;
			map[i][j] = 0;
			vs[i][j] = 0;
			visited[i][j] = 1000000;
		}
	}
}

// Nhap - Xuat
void nhap(){
	cin >> N >> M;
	cin >> x_start >> y_start;

	reset();
	map[x_start - 1][y_start - 1] = 1;

	cin >> numFires;
	for(int i = 0; i < numFires; i++){
		int x, y;
		cin >> x >> y;
		fires[x - 1][y - 1] = 1;
		fires_index[i][0] = x - 1;
		fires_index[i][1] = y - 1;
	}

	cin >> numLakes;
	for(int i = 0; i < numLakes; i++){
		int x, y;
		cin >> x >> y;
		map[x - 1][y - 1] = 3;
		fires[x - 1][y - 1] = -1;
	}

	cin >> numGates;
	for(int i = 0; i < numGates; i++){
		int x, y;
		cin >> x >> y;
		map[x - 1][y - 1] = 2;
	}

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

}
void xuat(){
	// Map
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;

	//// Fires
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cout << fires[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;

	// Diamonds
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cout << diamonds[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;

	// Visited
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cout << visited[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

// Check
bool check(int x, int y){
	return x >= 0 && x < N && y >= 0 && y < M;
}

// BFS
void BFS(int x, int y){
	front = rear = -1;
	push(x,y);
	visited[x][y] = 1;

	while(!isEmpty()){
		int topx = qx[front];
		int topy = qy[front];
		pop();

		for(int i = 0; i < 4; i++){
			int x1 = topx + dx[i];
			int y1 = topy + dy[i];

			if(check(x,y) && fires[x1][y1] == 0 && visited[x1][y1] > visited[topx][topy]){
				if(visited[x1][y1] > visited[topx][topy] + 1){
					visited[x1][y1] = visited[topx][topy] + 1;
					push(x1, y1);
				}
			}
		}
	}
}

void Try(int x, int y, int point, int time){
	vs[x][y] = 1;

	if(map[x][y] == 2){
		if(point > ans) ans = point;
	}

	for(int i = 0; i < 4; i++){
		int x1 = x + dx[i];
		int y1 = y + dy[i];

		if(check(x1, y1) && vs[x1][y1] == 0){
			int t = map[x1][y1] == 3 ? 2 : 1;

			if(time + t < visited[x1][y1]){
				Try(x1, y1, point + diamonds[x1][y1], time + t);
				vs[x1][y1] = 0;
			}

		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int T; cin >> T;

	for(int tc = 1; tc <= T; tc++){
		nhap();

		// BFS fire
		for(int i = 0; i < numFires; i++){
			BFS(fires_index[i][0], fires_index[i][1]);
		}
		
		// Backtrack
		ans = -1;
		Try(x_start - 1, y_start - 1, diamonds[x_start - 1][y_start - 1], 1);
		cout << "Case #" << tc << endl;
		cout << (ans == -1 ? -1 : ans)  << endl;
	}

	return 0;
}