题目P1126

#include<bits/stdc++.h>
using namespace std;
const int dx[13]={0, 0,0,0,1,2,3,0,0,0,-1,-2,-3},dy[13]={0, 1,2,3,0,0,0,-1,-2,-3,0,0,0};
int n,m,sx,sy,ex,ey,iface,mp[51][51],stp[51][51];
bool vis[51][51];
char cface;
struct my_queue{
    int x,y,step,f;
}que[5555];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m; //X Y
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            if(mp[i][j]==1){
                mp[i-1][j]=1;
                mp[i][j-1]=1;
                mp[i-1][j-1]=1;
            }
    }
    cin>>sx>>sy>>ex>>ey>>cface;
    switch(cface){
        case 'E': iface=1;break;
        case 'S': iface=2;break;
        case 'W': iface=3;break;
        case 'N': iface=4;break;
    }
    //
    vis[sx][sy]=1;
    int head=0,tail=1,nx,ny;
    que[head].x=sx;que[head].y=sy;que[head].step=0;que[head].f=iface;
    while(head<tail){
        for(int i=0;i<=3;i++){ //转向
            for(int j=1;j<=3;j++){ //1-3步
                int now_face=(que[head].f+i)%4;
                nx=que[head].x+dx[j*now_face];
                ny=que[head].y+dy[j*now_face];
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m && !mp[nx][ny]){
                    int z_face,t_step;
                    if(j==3) if(que[head].x+dx[(j-1)*now_face]<1||que[head].x+dx[(j-1)*now_face]>n||que[head].y+dy[(j-1)*now_face]<1||que[head].y+dy[(j-1)*now_face]>m) continue; //防止穿墙
                    if(i!=0) z_face= i%2==0?2:1;
                    t_step = que[head].step+1+z_face;
                    if(!vis[nx][ny] || (vis[nx][ny]&&t_step<stp[nx][ny]) ){
                        que[tail].x=nx; que[tail].y=ny; que[tail].f=(que[head].f+i)%4;
                        que[tail++].step=t_step;
                        vis[nx][ny]=1;
                        stp[nx][ny]=t_step;
                    }
                }
            }
        }
        head++;
    }
    //
    if(stp[ex][ey]==0&&!vis[ex][ey]){ cout<<-1;return 0; }
    cout<<stp[ex][ey];
    return 0;
}