题目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;
}