```
#include <iostream>
#include <cstring>
using namespace std;
const int NR=55,QR=2e6+5;
int n,m,a[NR][NR],ax,ay,bx,by,az,dis[NR][NR][6],vis[NR][NR][6];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char bz;
struct node
{
int x,y,z;
};
node q[QR];
int fr=1,bk=0;
bool check(int x,int y)
{
if(x>=n||y>=m) return false;
if(a[x][y]||a[x+1][y]||a[x][y+1]||a[x+1][y+1]) return false;
if(x<1||y<1||x>n||y>m) return false;
return true;
}
int bfs(int x,int y,int z)
{
q[++bk]=(node){x,y,z};
memset(dis,-1,sizeof(dis));
vis[x][y][z]=1; dis[x][y][z]=0;
while(fr<=bk)
{
node o=q[fr++];
if(o.x==bx&&o.y==by) return dis[o.x][o.y][o.z];
node p1=(node){o.x+dx[o.z],o.y+dy[o.z],o.z};
node p2=(node){o.x+dx[o.z]*2,o.y+dy[o.z]*2,o.z};
node p3=(node){o.x+dx[o.z]*3,o.y+dy[o.z]*3,o.z};
node p4=(node){o.x,o.y,(o.z+1)%4};
node p5=(node){o.x,o.y,(o.z-1+4)%4};
if(check(p1.x,p1.y))
{
if(!vis[p1.x][p1.y][p1.z])
{
vis[p1.x][p1.y][p1.z]=1;
dis[p1.x][p1.y][p1.z]=dis[o.x][o.y][o.z]+1;
q[++bk]=(node){p1.x,p1.y,p1.z};
}
if(check(p2.x,p2.y))
{
if(!vis[p2.x][p2.y][p2.z])
{
vis[p2.x][p2.y][p2.z]=1;
dis[p2.x][p2.y][p2.z]=dis[o.x][o.y][o.z]+1;
q[++bk]=(node){p2.x,p2.y,p2.z};
}
if(check(p3.x,p3.y))
{
if(!vis[p3.x][p3.y][p3.z])
{
vis[p3.x][p3.y][p3.z]=1;
dis[p3.x][p3.y][p3.z]=dis[o.x][o.y][o.z]+1;
q[++bk]=(node){p3.x,p3.y,p3.z};
}
}
}
}
if(!vis[p4.x][p4.y][p4.z])
{
vis[p4.x][p4.y][p4.z]=1;
dis[p4.x][p4.y][p4.z]=dis[o.x][o.y][o.z]+1;
q[++bk]=(node){p4.x,p4.y,p4.z};
}
if(!vis[p5.x][p5.y][p5.z])
{
vis[p5.x][p5.y][p5.z]=1;
dis[p5.x][p5.y][p5.z]=dis[o.x][o.y][o.z]+1;
q[++bk]=(node){p5.x,p5.y,p5.z};
}
}
return -1;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) cin>>a[i][j];
}
cin>>ax>>ay>>bx>>by>>bz;
if(bz=='W') az=3;
if(bz=='N') az=2;
if(bz=='S') az=0;
if(bz=='E') az=1;
cout<<bfs(ax,ay,az);
return 0;
}
```
by zhouyoyo @ 2024-02-21 16:41:45