Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
2.7 kB
2
Indexable
Never
#include <iostream>

using namespace std;

int T, N, M;
char arr[105][105];
int visited[105][105];

int spinX[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int spinY[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

int X[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int Y[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

class Queue{
        int front, rear;
        int q[1000000];
    public:
        Queue();
        void enQueue(int value);
        int deQueue();
        void reset();
        bool is_Empty();
};

Queue::Queue(){
    front = rear = -1;
}
void Queue::enQueue(int value){
    q[++rear] = value;
}
int Queue::deQueue(){
    return q[++front];
}
void Queue::reset(){
    front = rear = -1;
}
bool Queue::is_Empty(){
    if(front == rear)
        return true;
    return false;
}
Queue rQueue, cQueue;

int main(){
    freopen("input.txt", "rt", stdin);
    cin >> T;
    for(int tc = 1; tc <= T; tc++){
        cin >> M >> N;;
		int a, b, c, d;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                visited[i][j] = 0;
                cin >> arr[i][j];
                if(arr[i][j] == 'A'){
					a = i;
					b = j;
                }
                if(arr[i][j] == 'B'){
                    c = i;
                    d = j;
                }
            }
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] == 'Z'){
                    visited[i][j] = -1;
                    for(int k = 0; k < 8; k++){
                        int row = i + spinX[k];
                        int col = j + spinY[k];
                        if(row >= 0 && row < N && col >= 0 && col < M && visited[row][col] == 0 && arr[row][col] != 'B' ){
                            visited[row][col] = -1;
                        }
                    }
                }
            }
        }
        rQueue.reset();
        cQueue.reset();

        visited[a][b] = 1;

        rQueue.enQueue(a);
        cQueue.enQueue(b);

        while(!rQueue.is_Empty()){
            int cr = rQueue.deQueue();
            int cc = cQueue.deQueue();
            for(int i = 0; i < 8; i++){
                int nr = cr + X[i];
                int nc = cc + Y[i];
                if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0){
                    visited[nr][nc] = visited[cr][cc] + 1;
                    rQueue.enQueue(nr);
                    cQueue.enQueue(nc);
                }
            }
        }
        if(visited[c][d] == 0){
            cout << -1 << endl;
        }else{
            cout << visited[c][d] - 1 << endl;
        }
    }
    return 0;
}
Leave a Comment