Untitled

Hugo chay lua


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ớisố 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.
 
Input
Dòng đầu là số lượng test case T (T <= 50).
Dòng đầu của mỗi test case là 4 số N, M, SR, SC tương ứng là số hàng, số cột của khu rừng và tọa độ hàng, cột mà Hugo đang đứng. ( 4 <= N, M <= 15).
3 dòng tiếp theo, bắt đầu của mỗi dòng tương ứng là số lượng K các đám cháy hiện có, các hồ và các lối thoát, 2K số tiếp theo trên dòng là tọa độ tương ứng. N dòng tiếp theo sẽ là bản đồ mô tả số lượng kim cương D tại mỗi khu vực trong khu rừng. (0 <= D <= 1000)
Output
In mỗi test case trên 2 dòng, dòng đầu tiên là "Case #x", với x là số thứ tự của test case.
Dòng tiếp theo là số lượng kim cương lớn nhất mà Hugo có thể thu được, nếu Hugo không thể thoát ra khỏi khu rừng, in ra -1.
Sample
Input
5 <- Số lượng test case
4 4 1 2 <- Test case 1, khu rừng có kích thước 4x4, Hugo đang ở ô (1, 2)
2 1 1 4 1 <- 2 Khu vực bắt đầu cháy ở (1, 1) và (4, 1)
4 1 3 2 1 3 3 3 4 <- 4 Khu vực là hồ ở (1, 3), (2, 1), (3, 3) và (3, 4)
2 2 4 3 4 <- 2 lối thoát ở ô (2, 4) và (3, 4)
0 0 10 20 <- Số lượng kim cương hàng 1
9 3 2 5 <- Số lượng kim cương hàng 2
0 0 0 0 <- Số lượng kim cương hàng 3
0 10 0 100 <- Số lượng kim cương hàng 4
...
Output
Case #1
10  <- Số lượng kim cương lớn nhất mà Hugo có thể thu được
Case #2
45
Case #3
250
Case #4
643
Case #5
328




Code:
#include<iostream>
#define max 1000000
using namespace std;
int N,M,sr,sc;
int map[20][20];
int chay[20][20];
int ho[20][20];
int thoat[20][20];
int visit[20][20];
int queue[2][1005];
int front= -1;
int	rear=-1;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int kq;
int tongKC;
void pushq(int x,int y){
	if(rear == max-1) rear =-1;
	rear++;
	queue[0][rear]=x;
	queue[1][rear]=y;
}

void pop(){
	if(front == max-1) front =-1;
	front++;
	
}
bool IsEmpty(){
	return front == rear;
}
bool checkIn(int i, int j){
	if(i>0 && i<=N && j >0 && j <=M) return true;
	return false;
}
void reset(){
	 for (int i=0;i<20;i++){
        for (int j=0;j<20;j++){
            chay[i][j] = 1000000;
            ho[i][j] = 0;
            thoat[i][j] = -1;
			map[i][j] =0;
			visit[i][j]=0;
		}
	 }
	 front = rear =-1;
}
void bfs(){ //bfs de loang het lua ra toan ban do, luu lai tgian loang lua ra tung o
	while(!IsEmpty()){
		pop();
		int i1 = queue[0][front];
		int j1= queue[1][front];
		for(int i=0; i<4; i++){
			int i2 = i1 + dx[i];
			int j2 = j1 + dy[i];
			if(checkIn(i2, j2) && chay[i2][j2] > chay[i1][j1]+1 && ho[i2][j2] == 0){
				chay[i2][j2] = chay[i1][j1] +1;
				pushq(i2,j2);
			}
		}
	}
}

void backtrack(int i1, int j1, int t){
	tongKC+=map[i1][j1];
	if(thoat[i1][j1] == 1 && kq < tongKC) kq = tongKC;
	for(int i=0; i<4; i++){
			int i2 = i1 + dx[i];
			int j2 = j1 + dy[i];
			if(checkIn(i2, j2) && visit[i2][j2] == 0){
				if(ho[i2][j2] == 1){
					visit[i2][j2] =1;
					
					backtrack(i2,j2, t+2);
					tongKC-=map[i2][j2];
					visit[i2][j2] =0;
			
				}
				else if(ho[i2][j2] == 0 && t+1 < chay[i2][j2]){
					visit[i2][j2] =1;
					
					backtrack(i2,j2, t+1);
					tongKC-=map[i2][j2];
					visit[i2][j2] =0;
				
				}
			}
	}
}

int main(){
	freopen("Text.txt", "r", stdin);
	int test;
	cin >> test;
	for(int tc =1; tc<=test; tc++){
		cin >> N >> M >> sr >> sc;
		reset();
		int n,x,y;
        cin>>n;       // input chay
        for (int i=0;i<n;i++){
            cin>>x>>y;
            chay[x][y] = 0;
			pushq(x,y);
        }

		cin>>n;       // input ho
        for (int i=0;i<n;i++){
            cin>>x>>y;
            ho[x][y] = 1;
        }
		cin>>n;// input thoat
        for (int i=0;i<n;i++){
            cin>>x>>y;
            thoat[x][y] = 1;
        }
        // input kim cuong
        for (int i=1;i<=N;i++){
            for (int j=1;j<=M;j++) {
                cin>>map[i][j];
            }
        }
		bfs();
		visit[sr][sc] = 1;
		kq=-1;
		tongKC= 0;
		backtrack(sr,sc,0);
		cout << "Case #" << tc << endl;
		cout << kq << endl;

	}
	return 0;
}