Untitled

Hugo vuot lua lay kim cuong
Có thử thách dành cho Hugo như sau: Hugo được thả vào 1 khu rừng có rất nhiều kim cương, tuy nhiên đồng thời lúc đó có các đám cháy xuất hiện. Các đám cháy này sẽ lây lan ra các khu vực lân cận theo bốn hướng sau 1 giờ. Tuy nhiên trong khu rừng có một số hồ nhỏ, và lửa không thể cháy lan trên hồ.

Thời gian để Hugo di chuyển giữa các khu đất là 1 giờ, qua khu hồ là 2 giờ. Hãy giúp Hugo thoát khỏi khu rừng cùng với số lượng kim cương lớn nhất có thể và đảm bảo Hugo không bị lửa thiêu.

Lưu ý khu rừng chỉ tồn tại một số lượng nhất định lối thoát, tại danh giới của khu rừng, và Hugo không bao giờ quay lại khu vực mình đã đi qua.
#include<iostream>
using namespace std;

int T, hang, cot, vtdx, vtdy;
int map[25][25], visit[25][25], diamond[25][25], fire_lake[25][25], out[25][25];
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) {
	if(out[x][y]) {
		rs=max(rs,count1);
	}


	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]) {
			if(map[xn][yn] == 0 && 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(map[xn][yn] == 1 && check + 2 < fire_lake[xn][yn]) {
				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;
				map[i][j] = 0;
			}
		}
		//chay
		cin >> n;
		for(int i = 0; i < n; i ++) {
			cin >> x >> y;
			fire_lake[x-1][y-1] = 0;
			map[x-1][y-1] = 2;
		}
		//ho
		cin >> n;
		for(int i = 0; i < n; i ++) {
			cin >> x >> y;
			fire_lake[x-1][y-1] = 100000;
			map[x-1][y-1] = 1;
		}
		//thoat
		cin >> n_out;
		for(int i = 0; i < n_out; 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;
		bfs();
		for(int i = 0; i < hang; i ++) {
			for(int j = 0; j < cot; j ++) {
				visit[i][j] = 0;
			}
		}
		visit[vtdx][vtdy] = 1;
		dequy(vtdx, vtdy, 0, diamond[vtdx][vtdy]);
		if(rs == 0) cout << "Case #" << test_case << endl << -1 << endl;
		else cout << "Case #" << test_case << endl << rs << endl;
	}
	return 0;
}