https://ac.nowcoder.com/acm/contest/6164/A

#include<bits/stdc++.h>
using namespace std;
const int maxn=400;
int head[maxn],mp[200][200],cnt,tx,ty,n,dis[maxn][maxn],vis[maxn][maxn];
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//0==下，1==上，2==右，3==左
struct edge{
    int nx,to,w;
}e[6*maxn];
struct node{
    int x,y,cost,dir;
    friend bool operator  < (const node &a,const node &b){
        return a.cost>b.cost;
    }
};
void dijstra(int sx,int sy,int dir)//dir表示前一个点从哪个方向到达该点
{
    priority_queue<node> q;
    if(sx<=0||sy<=0||sx>n||sy>n||mp[sx][sy]) return;
    dis[sx][sy]=0;
    q.push(node{sx,sy,0,dir});
    while(!q.empty())
    {
        node k=q.top();q.pop();
        int x=k.x,y=k.y,di=k.dir;
        if(vis[x][y]) continue;
        vis[x][y]=1;
        for(int i=0;i<4;i++)
        {
            int dx=x+d[i][0],dy=y+d[i][1];
            if(dx<=0||dy<=0||dx>n||dy>n) continue;
            if(mp[dx][dy]) continue;
            int c=0;
            if(di!=i) c=1;//根据贪心思想，不可能在往回走，所以直接判断即可
            if(dis[dx][dy]>dis[x][y]+c){
                dis[dx][dy]=dis[x][y]+c;
            q.push(node{dx,dy,dis[dx][dy],i});
            }
        }
    }
}
int main()
{
    int sx,sy;
    memset(dis,0x3f,sizeof(dis));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char ch;
            cin>>ch;
            if(ch=='A') sx=i,sy=j;
            if(ch=='B') tx=i,ty=j;
            if(ch=='x') mp[i][j]=1;
        }
    }
    int ans=1e8;
    for(int i=0;i<4;i++)
    {
        dijstra(sx+d[i][0],sy+d[i][1],i);//起点从四个方向分别开始
        ans=min(ans,dis[tx][ty]);
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
    }
    if(ans>=0x3f) cout<<-1<<endl;
    else cout<<ans<<endl;
}