Hugo_trongrung

HuGo_trongrung
#include <iostream>

using namespace std;
int M, N, xH, yH, ans;
int dim[17][17];
int visit[17][17];
int Lake[17][17];
int Out[17][17];
int fire[17][17];
int numL, xL, yL;
int numF, xF, yF;
int numO, xO, yO;
int front, rear;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

struct Node{
    int r,c;
};

Node queue[100000];

void enQueue(int x, int y){
    Node node; node.r = x; node.c = y;
    rear++;
    queue[rear] = node;
}

Node deQueue(){
    front++;
    return queue[front];
}


void BFS(){
    while (front != rear)
    {
        Node mid = deQueue();
        for (int i = 0; i < 4; i++)
        {
            int tx = mid.r + dx[i];
            int ty = mid.c + dy[i];
            if (tx > 0 && tx <= M && ty > 0 && ty <= N && fire[tx][ty] > fire[mid.r][mid.c] + 1 && Lake[tx][ty] == 0)
            {
                fire[tx][ty] = fire[mid.r][mid.c] + 1;
                enQueue(tx,ty);
            }
        }
    }
}

void backtrack(int x, int y, int cnt){

    if(visit[x][y] >= fire[x][y]){
        return;
    }

    if(Out[x][y] == 3){
        if(cnt > ans){
            ans = cnt;
        }
    }

    for (int i = 0; i < 4; i++)
    {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (tx > 0 && tx <= M && ty > 0 && ty <= N && visit[tx][ty] == -1)
        {

            if (Lake[tx][ty] == 2)
            {
                visit[tx][ty] = visit[x][y] + 2;
            } else
            {
                visit[tx][ty] = visit[x][y] + 1;
            }
            
            backtrack(tx,ty,cnt + dim[tx][ty]);

            visit[tx][ty] = -1;

        }

    }

}

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

    for (tc = 1; tc <= T; tc++)
    {
        cin >> M >> N >> xH >> yH;
        ans = -1;
        for (int i = 1; i <= M; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                fire[i][j] = 10000;
                Lake[i][j] = 0;
                Out[i][j] = 0;
                visit[i][j] = -1;
            }
        }

        // chay
        cin>> numF;
        front = rear = -1;
        for (int i = 0; i < numF; i++)
        {
            cin>> xF>> yF;
            fire[xF][yF] = 0;
            enQueue(xF,yF);
        }

        // ho
        cin>> numL;
        for (int i = 0; i < numL; i++)
        {
            cin>> xL >> yL;
            fire[xL][yL] = 10000;
            Lake[xL][yL] = 2;
        }
        
        // loi thoat
        cin>> numO;
        for (int i = 0; i < numO; i++)
        {
            cin>> xO >> yO;
            Out[xO][yO] = 3;
        }

        // nhap dimond

        for (int i = 1; i <= M; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                cin>> dim[i][j];
            }
        }
        BFS();
        visit[xH][yH] = 0;
        backtrack(xH,yH,dim[xH][yH]);

        cout<< "Case #" << tc << endl;
        if(ans > 0){
            cout<< ans << endl;
        }else
        {
            cout<< "-1" << endl;
        }

    }
    return 0;
}