Untitled

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

using namespace std;

int map[100][100];
int visit[100][100];
int M, N;

int dx[8] = {-1,-1,-2,-2,2,2,1,1};
int dy[8] = {-2,2,-1,1,-1,1,-2,2};

int kR[8] = {-1,0,1,1,1,0,-1,-1};
int kC[8] = {-1,-1,-1,0,1,1,1,0};

struct node{
    int r, c;
} Queue[10000];
int front, rear;
void init(){
    front = rear = -1;
    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++)
            visit[i][j]=0;
}
void push(int r, int c){
    rear++;
    Queue[rear].r = r;
    Queue[rear].c = c;
}
node pop(){
    return Queue[++front];
}
bool isEmpty(){
    return front==rear;
}

node Start, End, temp;

int bfs(){
    init();
    push(Start.r, Start.c);
    visit[Start.r][Start.c]=1;

    while(!isEmpty()){
        node cur = pop();
        if(cur.r==End.r && cur.c==End.c) return visit[cur.r][cur.c]-1;
        for(int i=0; i<8; i++){
            temp.r = cur.r + kR[i];
            temp.c = cur.c + kC[i];
            if(temp.r >= N || temp.c >= M || temp.r < 0 || temp.c < 0 || visit[temp.r][temp.c]!=0 || map[temp.r][temp.c]==1 || map[temp.r][temp.c]==2) continue;
            push(temp.r, temp.c);
            visit[temp.r][temp.c] = visit[cur.r][cur.c] + 1;
        }
    }
    return -1;
}



int main(){
    //freopen("input.txt", "r", stdin);
    int T;
    cin >> T;
    for(int tc=1; tc<=T; tc++){
        cin >> M >> N;
        char ck;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map[i][j]=0;
                cin >> ck;
                if(ck=='.'){
                    map[i][j]=0;
                    continue;
                }
                if(ck=='Z'){
                    map[i][j]=1;
                    continue;
                }
                if(ck=='A'){
                    Start.r = i;
                    Start.c = j;
                    continue;
                }
                if(ck=='B'){
                    End.r = i;
                    End.c = j;
                    continue;
                }
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j]==1){
                    for(int k=0; k<8; k++)
                        if(i+dx[k]<N && i+dx[k]>=0 && j+dy[k] < M && j+dy[k] >= 0 && map[i+dx[k]][j+dy[k]]!=1)
                            map[i+dx[k]][j+dy[k]] = 2;
                }
            }
        }
        map[End.r][End.c] = 0;
        cout << bfs() << endl;
    }
    return 0;
}
Leave a Comment