mario_climb_chatnhiphan

 avatar
duyvan
plain_text
a year ago
2.7 kB
5
Indexable
//mario climb
#include <iostream>

using namespace std;
int M, N;
int xS, yS, xE, yE;
int front, rear;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int A[55][55];
int visit[55][55];
int ans;

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 resetVisit(){
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            visit[i][j] = 0;
        }
    }
}



int check(int k){
    resetVisit();
    front = rear = -1;
    enQueue(xS,yS);
    visit[xS][yS] = 1;

    while (front!=rear)
    {
        Node mid = deQueue();
        if(mid.r == xE && mid.c == yE){
            return 1;
        }

        for (int i = 2; i <= 3; i++)
        {
            for (int j = 1; j <= k; j++)
            {
                int tx = mid.r + dx[i] * j;
                int ty = mid.c + dy[i];
                if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3))
                {
                    enQueue(tx,ty);
                    visit[tx][ty] = 1;
                }
            }
        }

        for (int i = 0; i < 2; i++)
        {
            int tx = mid.r + dx[i];
            int ty = mid.c + dy[i];
            if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3))
                {
                    enQueue(tx,ty);
                    visit[tx][ty] = 1;
                }
        }
    }

    return 0;

}

int fun(int s, int e){
    int mid = s + (e - s)/2;
    if (check(mid-1) == 0 && check(mid) == 1)
    {
        return mid;
    }

    if(check(mid) == 1){
        return fun(s,mid);
    }else
    {
        return fun(mid+1,e);
    }
}

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

    for (tc = 1; tc <= T; tc++)
    {
        cin >> M >> N;
        ans = 0;

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cin>> A[i][j];
                if(A[i][j] == 2){
                    xS = i;
                    yS = j;
                }
                if (A[i][j] == 3)
                {
                    xE = i;
                    yE = j;
                }
            }
        }

        ans = fun(1,50);
        cout<< "Case #" << tc <<endl;
        cout<< ans << endl;

    }


    return 0;
}
Leave a Comment