题目大意：
给定一个N*N的矩阵，并告诉你每一个格子能否经过，要求你求出(n,1)到(1,n)的最短路径的操作数。
其中操作有2种，第一种是沿着目前的方向走一格，第二种是向左或向右转90°
由于题目设置，一开始我们并不知道起点的方向，所以也可以理解为要我们求出朝向不同但位置相同的2个点的最短路径的方案数，但是注意，此时2个点的操作必须同时进行，比如要前进必须同时前进。
如果某一个点走到了边界外或者走到了不能经过的格子，那么他会返回并且不进行任何操作
如果一个点走到了终点那么接下来的指令它都不会执行
————————————————我是分割线————————————————
这道题目，很显然就是求最短路，然后我们自然会想到spfa
但是这个题目坑就坑在dis数组，由于我们有2个点，而且每个点都有方向，所以是6维的
dis[x1][y1][x2][y2][d1][d2]表示两个点分别从起点走到(x1,y1)方向为d1;走到(x2,y2)方向为d2
然后我们只要初始化后直接SPFA即可
记得check一下有没有超边界。
至于注意事项吗，就是别打挂了。。。暴力调了半小时。。。。。
#include<cstdio>
#include<queue>
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 0x3f3f3f3f
#define MN 21
using namespace std;
int m[MN][MN],dis[MN][MN][MN][MN][][];
int h[]={,-,,,},l[]={,,,,-};
int nowx1,nowx2,nowy1,nowy2,sum1,sum2,td1,td2,ans,n;
bool c[MN][MN][MN][MN][][];
char ch;
struct gather{
int x1,y1,x2,y2,d1,d2;
gather(int x1,int y1,int x2,int y2,int d1,int d2):
x1(x1),y1(y1),x2(x2),y2(y2),d1(d1),d2(d2){}
gather () {}
};
queue<gather>q;
bool check(int x,int y){
if((x<)||(x>n)||(y<)||(y>n))return false;
return true;
}
void spfa()
{
q.push(gather(n,,n,,,));
c[n][][n][][][]=true;
while(!q.empty()){
gather p=q.front();
q.pop();
nowx1=p.x1+h[p.d1];nowx2=p.x2+h[p.d2];
nowy1=p.y1+l[p.d1];nowy2=p.y2+l[p.d2];
if((!check(nowx1,nowy1))||(!m[nowx1][nowy1]))nowx1=p.x1,nowy1=p.y1;
if((!check(nowx2,nowy2))||(!m[nowx2][nowy2]))nowx2=p.x2,nowy2=p.y2;
if(p.x1==&&p.y1==n)nowx1=,nowy1=n;
if(p.x2==&&p.y2==n)nowx2=,nowy2=n;
sum1=dis[nowx1][nowy1][nowx2][nowy2][p.d1][p.d2];
sum2=dis[p.x1][p.y1][p.x2][p.y2][p.d1][p.d2];
if(sum1>sum2+)
{
dis[nowx1][nowy1][nowx2][nowy2][p.d1][p.d2]=sum2+;
if(!c[nowx1][nowy1][nowx2][nowy2][p.d1][p.d2])
q.push(gather(nowx1,nowy1,nowx2,nowy2,p.d1,p.d2));
c[nowx1][nowy1][nowx2][nowy2][p.d1][p.d2]=;
}
td1=(p.d1==)?:p.d1-;td2=(p.d2-==)?:p.d2-;
sum1=dis[p.x1][p.y1][p.x2][p.y2][td1][td2];
if(sum1>sum2+)
{
dis[p.x1][p.y1][p.x2][p.y2][td1][td2]=sum2+;
if(!c[p.x1][p.y1][p.x2][p.y2][td1][td2])
q.push(gather(p.x1,p.y1,p.x2,p.y2,td1,td2));
c[p.x1][p.y1][p.x2][p.y2][td1][td2]=;
}
td1=p.d1==?:p.d1+;td2=p.d2==?:p.d2+;
sum1=dis[p.x1][p.y1][p.x2][p.y2][td1][td2];
if(sum1>sum2+)
{
dis[p.x1][p.y1][p.x2][p.y2][td1][td2]=sum2+;
if(!c[p.x1][p.y1][p.x2][p.y2][td1][td2])
q.push(gather(p.x1,p.y1,p.x2,p.y2,td1,td2));
c[p.x1][p.y1][p.x2][p.y2][td1][td2]=;
}
c[p.x1][p.y1][p.x2][p.y2][p.d1][p.d2]=false;
}
} int main(){
freopen("GP3.in","r",stdin);
freopen("GP3.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%c",&ch);
for(int j=;j<=n;j++)
{
scanf("%c",&ch);
if(ch=='E')m[i][j]=true;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
for(int k=;k<=n;k++)
for(int l=;l<=n;l++)
for(int dd1=;dd1<=;dd1++)
for(int dd2=;dd2<=;dd2++)
dis[i][j][k][l][dd1][dd2]=inf;
dis[n][][n][][][]=;
ans=inf;
spfa();
for(int i=;i<=;i++)
for(int j=;j<=;j++)
ans=min(ans,dis[][n][][n][i][j]);
printf("%d\n",ans);
fclose(stdin);
fclose(stdout);
}