题目链接：
发一个不一样的题解
算法:
标签是spfa或DP，有的人用spfa，有的人用bfs，有的人用dfs，可我用的居然是用双端队列的bfs。
思路：
这一题可以看成一个最短路。对于某个点，它有四种状态，面对前、后、左、右，所以我们可以把一个点分成四个点。
由于我们要求的不是最要需要多少步，而是最要需要拐多少弯，所以边权有两种，0(不拐弯)和1(拐弯)。此时，用普通的bfs就不行了，可以改成spfa。(平均时间复杂度：(k·n^2,k)为小常数，最坏可达(n^2))。
用spfa算法会使一个点被扩张多次，使效率降低。但最短路还有另一个更高效的Dijkstra算法。朴素的Dijkstra算法是点数的平方，一般可以加堆优化。但堆优化会增加一个log，在这一题会得不偿失(平均时间复杂度：(n^2logn^2，logn^2)为堆的时间)。
不过，这一题的边权不是为零就是一，并不要用堆，用双端队列就行。在普通bfs队列里，按层扩张，层数只有两层，正在扩张层和扩张层的下一层，而且正在扩张层在队列中全部在下一层的前面。如果改成双端队列，边权为零说明新扩张的结点和扩张它的结点在同一层，从队头入队；否则，从队尾入队。这样，当一个点第一次被取出时，它离起点的距离就它离起点的最短路。(平均时间复杂度：(n^2))
code:
双端队列bfs:
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};//四个方向
char a[110][110];//原地图
int v[110][110][4];//拆点后的单源最短路
bool b[110][110][4];//记录是否被取出
struct node{
int x,y,f;
};
deque<node>q;//STL中的双端队列
int main()
{
memset(v,0x3f,sizeof(v));//最短路初值为inf
int n,sx,sy,tx,ty;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
if(a[i][j]=='A')//起点
{
sx=i;
sy=j;
}
else if(a[i][j]=='B')//终点
{
a[i][j]='.';
tx=i;
ty=j;
}
}
for(int k=0;k<4;k++)//将起点入队
q.push_back((node){sx,sy,k}),v[sx][sy][k]=0;
while(!q.empty())//dijkstra
{
node x=q.front();
q.pop_front();
if(x.x==tx&&x.y==ty)//终点被取出，得到答案
{
printf("%d
",v[x.x][x.y][x.f]);
return 0;
}
if(b[x.x][x.y][x.f])continue;//被取出过，continue
b[x.x][x.y][x.f]=1;
for(int i=0;i<4;i++)//枚举四个方向
{
int x1=x.x+dx[i],y1=x.y+dy[i];
if(a[x1][y1]=='.'/*越界即为空字符*/&&v[x.x][x.y][x.f]+(x.f!=i)<v[x1][y1][i])
{
v[x1][y1][i]=v[x.x][x.y][x.f]+(i!=x.f);
if(i==x.f)q.push_front((node){x1,y1,i});//边权为零,从队头入队。
else q.push_back((node){x1,y1,i});//否则，从队尾入队
}
}
}
puts("-1");//终点从未被取出，判断无解
}