0 pts BFS 悬 3 关求调

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n;
int ans[N][N][4];
char sv[N][N];

struct node{
    int x, y, f, as;
}; queue <node> q;

int ax, ay, bx, by;

const int dx[] = {1, 0, 0, -1};
const int dy[] = {0, 1, -1, 0};

void bfs(){
    for (int i = 0; i < 4; i ++){
        q.push({ax, ay, i, 0});
    }

    while (q.size()){
        int x, y, t, as;
        x = q.front().x;
        y = q.front().y;
        t = q.front().f;
        as = q.front().as;
        q.pop();

        if (x < 0 || y < 0 || x >= n || y >= n) continue;
        if (sv[x][y] == 'x') continue;
        if (ans[x][y][t] <= as) continue;
        ans[x][y][t] = as;
        // printf("%d %d %d %d\n", x, y, t, as);
        if (x == bx && y == by) continue;
        q.push({x + dx[t], y + dy[t], t, as});
        for (int i = 0, p; i < 4; i ++){
            if (i == t) continue;
            if ((t == 1 && i == 3) || (t == 2 && i == 0) || (t == 3 && i == 1) || (t == 0 && i == 2)) p = 2;
            else p = 1;
            q.push({x + dy[t], y + dy[t], i, as + p});
        }
    }
}

int main(){
    cin >> n;
    for (int x = 0; x < n; x ++){
        for (int y = 0; y < n; y ++){
            for (int i = 0; i < 4; i ++) ans[x][y][i] = INT_MAX;
            cin >> sv[x][y];
            if (sv[x][y] == 'A') ax = x, ay = y;
            if (sv[x][y] == 'B') bx = x, by = y;
        }
    }

    bfs();
    int anss = INT_MAX;
    for (int i = 0; i < 4; i ++){
        anss = min(anss, ans[bx][by][i]);
    }
    if (anss == INT_MAX) cout << -1;
    else cout << anss;
}