玄关求条（90pts）（TLE on #4）

#include "bits/stdc++.h"
#define endl '\n'
#define mkp make_pair
using namespace std;
int n;
bool mp[105][105];
bool vis[105][105];
pair<int, int> st, ed;
int ans = 1e9;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void dfs(pair<int, int> pos, int turns, int dirc)
{
    if (turns >= ans)
    {
        return;
    }
    if (pos == ed)
    {
        ans = min(ans, turns);
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nx = pos.first + dx[i];
        int ny = pos.second + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > n || mp[nx][ny] || vis[nx][ny])
            continue;
        vis[nx][ny] = true;
        if (dirc == -1)
        {
            dfs(mkp(nx, ny), turns, i);
            vis[nx][ny] = false;
            continue;
        }
        bool orgdc = (dirc % 2);
        bool nowdc = (i % 2);
        if (orgdc != nowdc)
            dfs(mkp(nx, ny), turns + 1, i);
        else
            dfs(mkp(nx, ny), turns, i);
        vis[nx][ny] = false;
    }
}
int main()
{
    ios_base::sync_with_stdio(0), ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            char x;
            cin >> x;
            mp[i][j] = (x == 'x');
            if (x == 'A')
                st = mkp(i, j);
            else if (x == 'B')
                ed = mkp(i, j);
        }
    }
    dfs(st, 0, -1);
    cout << (ans == 1e9 ? -1 : ans) << endl;
}