题目考点：bfs or dfs or dijkstra(蒟蒻优先想到bfs，就先粘上bfs吧，日后有时间补上其他的)

题目大意：走迷宫起点到终点至少需要转90度弯共几次

题目分析：优先队列按照转弯次数从小到大，基于贪心思想得到最优解。在bfs版子的基础上，在结点中多加一个该点是从哪个方向走来的即可。 需要注意的是，我们走过的点不能单纯的标记走过后就不能再走，而是说走过该点之后，如果下次走到该点时，需要的转弯次数更少，或者走到该点时方向不同的话，还是要维护进队列的。（如下方样例）

卡bfs模板样例：

4
A . . .
. . . .
x x B .
. . . .
// 该样例从（2,2）或（1,3）都可以到（2,3），但是方向不同，也需要添加到队列

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;
int n, stx, sty, edx, edy;
char mp[N][N];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int v[N][N];

struct POS{
    int x, y, d, sum;  // x,y是坐标点,d是来的方向,sum是转弯次数
    bool operator > (const POS& A)const{
        return sum > A.sum;
    }
}pos[N*N];

priority_queue<POS, vector<POS>, greater<POS> > r;

int dfs(int x, int y, int dd)
{
    int cnt = INF;
    if(x<1 || x>n || y<1 || y>n || mp[x][y] == 'x')
        return INF;

    v[stx][sty] = v[x][y] = 0;
    r.push({x, y, dd, 0});

    while(r.size())
    {
        auto t = r.top(); r.pop();
        int xx = t.x, yy = t.y;
        int di = t.d, ct = t.sum;

        if(xx == edx && yy == edy)
            cnt = min(cnt, ct);
        //cout << xx << ' ' << yy << ":" ;
        for(int i = 0; i < 4; i++)
        {
            int tx = xx + dir[i][0], ty = yy + dir[i][1];
            if(mp[tx][ty] == 'x') continue;
            if(tx<1 || tx>n || ty<1 || ty>n)
                continue;
          
            int tt = ct;
            if(di != i) tt += 1;  // 方向不同，转弯数+1

            if(tt <= v[tx][ty])
            {
                r.push({tx, ty, i, tt});
                v[tx][ty] = tt;
                //cout << "(" << tx << ',' << ty << ")" << '-' << tt << ' ' ;
            }
        }
        //cout << '\n';
    }
    return cnt;
}

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    {
        scanf(" %c", &mp[i][j]);
        if(mp[i][j] == 'A')
            stx = i, sty = j;
        if(mp[i][j] == 'B')
            edx = i, edy = j;
    }

    int ans = INF;
    for(int i = 0; i < 4; i++)  // 由于开始方向未定，因此每个方向走一次
    {
        memset(v, 0x3f, sizeof v);
        while(r.size()) r.pop();
        int x = stx+dir[i][0], y = sty+dir[i][1];
        ans = min(ans, dfs(x, y, i));
    }
    if(ans == INF)
        printf("-1");
    else printf("%d", ans);

    return 0;
}
/*
3
A . .
. . .
x x B
*/