Untitled

#include <iostream>
using namespace std;
int N,M;
int MoveX[] = {0,0,1,-1};
int MoveY[] = {1,-1,0,0};
int Chay[20][20],Ho[20][20],Thoat[20][20],KC[20][20],VS[20][20];
int xHugo,yHugo;
int Q[2][1000000];
int front, rear;
int result;

void reset(){
    for (int i=0;i<20;i++){
        for (int j=0;j<20;j++){
            Chay[i][j] = 1000000;
            Ho[i][j] = -1;
            Thoat[i][j] = -1;
            KC[i][j] = 0;
            VS[i][j] = -1;
        }
    }
    front = -1;
    rear = -1;
    result = -1;
}

void BFS_Chay(){
    while (front<rear){
        front++;
        int x = Q[0][front];
        int y = Q[1][front];
        for (int i=0;i<4;i++){
            int xn = x+MoveX[i];
            int yn = y+MoveY[i];
            if (xn > 0 && xn < N && yn > 0 && yn < M 
                    && Chay[xn][yn] == 1000000 && Ho[xn][yn] == -1) {
                Chay[xn][yn] = Chay[x][y]+1;
                rear++;
                Q[0][rear] = xn;
                Q[1][rear] = yn;
            }
        }
    }
}

void BT_Hugo(int x, int y, int t, int kc){
    if (Thoat[x][y] == 1){
        result = kc>result?kc:result;
    }
    for (int i=0;i<4;i++){
        int xn = x+MoveX[i];
        int yn = y+MoveY[i];
        if (xn > 0 && xn < N && yn > 0 && yn < M && VS[xn][yn] == -1) {
            if (Ho[xn][yn] == 1) {
                VS[xn][yn] = 1;
                BT_Hugo(xn, yn, t+2, kc+KC[xn][yn]);
                VS[xn][yn] = -1;
            } else if (Ho[xn][yn] == -1 && t+1<Chay[xn][yn]){
                VS[xn][yn] = 1;
                BT_Hugo(xn, yn, t+1, kc+KC[xn][yn]);
                VS[xn][yn] = -1;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    int T;
    cin>>T;
    for(int tc=1;tc<=T;tc++){
        cin>>N>>M;
        N++;
        M++;
        cin>>xHugo>>yHugo;
        reset();
        int n,x,y;
        cin>>n;// input chay
        for (int i=0;i<n;i++){
            cin>>x>>y;
            Chay[x][y] = 0;
            rear++;
            Q[0][rear] = x;
            Q[1][rear] = 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>>KC[i][j];
            }
        }
        BFS_Chay();
        VS[xHugo][yHugo] = 1;
        BT_Hugo(xHugo, yHugo,0,KC[xHugo][yHugo]);
        cout<<"Case #"<<tc<<endl<<result<<endl;
    }
    return 0;
}