🎉🎉🎉🎉号外号外高校算法学习社区开始新活动啦🚩🚩🚩因为同学们的基础不一样，觉得原来的每日一题比较简单,所以我们决定开设一个普及组一个提高组🙇🙇🙇提高组由我负责，每日一题，我们一起卷起来🚀🚀🚀

🌴题目描述

每逢佳节胖三斤，牛牛在过去的节日里长胖了，连拐弯都困难，甚至会卡在门上，所以他很讨厌拐弯。给你一个$N\ast N(0\le N\le 100)$ 的方格中，‘x’表示障碍，‘.’表示没有障碍（可以走），牛牛可以从一个格子走到他相邻的四个格子，但是不能走出这些格子。问牛牛从A点到B点最少需要转90度的弯几次。

🌃解题报告

读完题之后就会发现这道题用bfs/dfs的方式很简单，但是这同时也是一个很好的建图的题。这道题用到的建图知识在做更复杂的题中很常用，所以最好学一下。

我们可以把转弯当作距离来建图，一条直线上的点可以当作是中间有一条距离为零的路径，可以通过转弯到达的两点间认为是有一条距离为一的路径。但是每一个点都是有四种状态的（从四个方向到达），所以我们在建图的时候可以把一个点拆成四个点去看

我们可以把一条边看作是一个方向来的，比如下面的边是从下往上走走到这一点的。然后就可以把一条边看作是一个点，然后24，13直接不涉及到转弯，就可以连一条距离为1的边，12，13，23，34涉及到转向，就可以连一条长度为1的边。特别的这样建图以后所有的转弯都发生在原来的图上的点内部，所以在建新图的时候如果要和别的点有联系，那么就是沿当前方向走能到达下一个点，所以特判一下能否到达下一个点然后连一条长度为零的边就行。
然后他有说起点可以是任意方向的嘛，那么拆点以后起点就可能有四个然后取一个最小值。我们其实就可以另外连一个超级源点，这个点到四个可能的起点都有一条长度为零的边，然后找最短路的时候起点就是这个新建的点。终点也可以同理，建一个新的点做终点。
然后怎么得到拆开点的编号呢？这里我们可以用一个哈希。想要把三个数字（原坐标x,y，还有一个表示方向的值）哈希成为一个数字，我们就可以借鉴一下我们字符串哈希的方式，把这三个数字当作一个P进制数字的三位。

建好图以后在新图上跑一遍最短路就可以了。这个就是模板了，最短路算法什么都可以。

🍬AC代码（c++）

#include<iostream>
#include<unordered_map>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int,int> PII;

const int N=1010,M=1e7+10;
char mp[N][N];
int h[M],ne[M],num[M],w[M];
int n,idx;
PII st,ed;

int dist[M],vis[M];

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

priority_queue<PII,vector<PII>,greater<>>qu;

void add(int a,int b,int c) {
    ne[idx]=h[a];
    num[idx]=b;
    w[idx]=c;
    h[a]=idx++;
}

int hash_(int a,int b,int c) {
    return c*n*n+(a-1)*n+b;
}

void dijkstra()
{
    memset(dist,0x3f,sizeof(dist));
    qu.push({0,M-2});
    dist[M-2]=0;
    while(qu.size())
    {
        PII t=qu.top();
        qu.pop();
        int distance=t.first;
        int yuandian=t.second;
        if(!vis[yuandian])
        {
            vis[yuandian]=true;
            for(int i=h[yuandian];i!=-1;i=ne[i])
            {
                int g=num[i];
                if(dist[g]>dist[yuandian]+w[i])
                {
                    dist[g]=dist[yuandian]+w[i];
                    qu.push({dist[g],g});
                }
            }
        }
    }
}

int main() {
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            cin>>mp[i][j];
            if(mp[i][j]=='A') st={i,j};
            else if(mp[i][j]=='B') ed={i,j};
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(mp[i][j]=='x') continue;
            for(int k=0;k<4;k++) {
                int a=hash_(i,j,k);
                int b=hash_(i,j,(k+1)%4);
                int c=hash_(i,j,(k+3)%4);
                int d=hash_(i,j,(k+2)%4);
                add(a,c,1),add(a,b,1),add(a,d,0);
                int x=i+dx[k],y=j+dy[k];
                if(x>0&&x<=n&&y>0&&y<=n&&mp[x][y]!='x') add(a,hash_(x,y,k),0);
            }
        }
    }
    
    for(int i=0;i<4;i++) add(M-2,hash_(st.first,st.second,i),0);
    for(int i=0;i<4;i++) add(hash_(ed.first,ed.second,i),M-1,0);

    dijkstra();
    
    if(dist[M-1]!=0x3f3f3f3f) cout<<dist[M-1];
    else cout<<-1;
}