30分求调
查看原帖
30分求调
943039
NKOJ_AKer楼主2024/8/5 15:12
#include<bits/stdc++.h>
using namespace std;
typedef int intt;
#define int long long
int n,m,a[55][55],sx,sy,ex,ey,vis[55][55][4],tto=0,ans=-1;
int fx[4][2]={0,-1,0,1,-1,0,1,0};
int l[]={3,2,0,1};
int r[]={2,3,1,0};
struct node{
	int x,y,t,step;
};
queue<node>q;
void fxto(char a){
	switch(a){
		case'N':tto=2;break;
		case'S':tto=3;break;
		case'W':tto=0;break;
		case'E':tto=1;break;
	}
}
void bfs(){
	while(!q.empty()){
		node tmp=q.front();
		q.pop();
		if(tmp.x==ex&&tmp.y==ey){
			ans=tmp.step;
			return;
		}
		node nx=tmp;
		for(int i=1;i<=3;i++){
			node nx;
			nx.x+=fx[tmp.t][0];
			nx.y=fx[tmp.t][1];
			if(nx.x<1||nx.y<1||nx.x>n||nx.y>m||a[nx.x][nx.y]){
				break;
			}
			if(vis[nx.x][nx.y][nx.t]){
				continue;
			}
			else{
				vis[nx.x][nx.y][nx.t]=1;
				nx.step=tmp.step+1;
				q.push(nx);
			}
		}
		nx=tmp;
		nx.step=tmp.step+1;
		nx.t=l[tmp.t];
		if(!vis[nx.x][nx.y][nx.t]){
			vis[nx.x][nx.y][nx.t]=1;
			q.push(nx);
		}
		nx.t=r[tmp.t];
		if(!vis[nx.x][nx.y][nx.t]){
			vis[nx.x][nx.y][nx.t]=1;
			q.push(nx);
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]){
				a[i-1][j]=1;
				a[i][j-1]=1;
				a[i-1][j-1]=1;
				a[i][j]=1;
			}
		}
	}
	cin>>sx>>sy>>ex>>ey;
	string h;
	cin>>h;
	fxto(h[0]);
	q.push((node){sx,sy,tto,0});
	vis[sx][sy][tto]=1;
	bfs();
	cout<<ans;
	return 0;
}

2024/8/5 15:12
加载中...