洛谷P1126

30分WA求调

#include <bits/stdc++.h>
using namespace std;
struct Node{
	int x,y,st,t;
}node;
int n,m,a[55][55],sx,sy,ex,ey,fx,z[55][55],f_[55][55];
char ch;
int zhuan[4]={1,2,1,0};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int ft[4]={1,4,2,3};
int fft[4]={1,3,4,2};
void init(){
	if(ch=='N') fx=1;
	else if(ch=='S') fx=2;
	else if(ch=='W') fx=3;
	else fx=4;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]==1){
				z[i-1][j]=1,z[i][j-1]=1;
				z[i-1][j-1]=1,z[i][j]=1;
			}
		}
	}
}
bool check(int x,int y){
	if(x>n-1||x<1||y<1||y>m-1||(x==sx&&y==sy)||z[x][y]==1) return 0;
	return 1;
}
void bfs(){
	node.x=sx,node.y=sy,node.st=0,node.t=fx;
	queue<Node> q;
	q.push(node);
	while(!q.empty()){
		Node f=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int _zhuan=zhuan[i];
			int f_x=fft[f.t]+i;
			if(f_x==4) f_x=0;
			else if(f_x==5) f_x=1;
			else if(f_x==6) f_x=2;
			else if(f_x==7) f_x=3;
			f_x=ft[f_x];
			for(int j=0;j<3;j++){
				int _dx=f.x+dx[f_x]*j;
				int _dy=f.y+dy[f_x]*j;
				if(!check(_dx,_dy)) break;
				if(f.st+_zhuan+1<f_[f.x+dx[f_x]*j][f.y+dy[f_x]*j]||f_[f.x+dx[f_x]*j][f.y+dy[f_x]*j]&&z[f.x+dx[f_x]*j][f.y+dy[f_x]*j]==0){
					Node d;
					d.x=f.x+dx[f_x]*j;
					d.y+f.y+dy[f_x]*j;
					d.t=f_x;
					d.st=f.st+_zhuan+1;
					f_[f.x+dx[f_x]*j][f.y+dy[f_x]*j]=d.st;
					q.push(d);
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
	cin >> ch;
	init();
	bfs();
	if(f_[ex][ey]==0&&(ex!=sx||ey!=sy)) printf("-1");
	else printf("%d",f_[ex][ey]);
	return 0;
}