第三次求助,悬赏一关注!
查看原帖
第三次求助,悬赏一关注!
658786
STUDENT00楼主2022/11/5 11:15
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,ex,ey,sd,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
bool t[55][55],vis[55][55][4];
struct node{
	int x,y,d,s;
};
char c[1];
queue<node> q;
bool check2(int x,int y){
	return x>=1&&x<n&&y>=1&&y<m&&!(t[x][y]||t[x+1][y]||t[x][y+1]||t[x+1][y+1]);
}
void put(int a,int b,int c,int d){
	node t;
	t.x=a;
	t.y=b;
	t.d=c;
	t.s=d;
	q.push(t);
}
int aa(int t){
	if(t<3) return t+1;
	return 0;
}
int bb(int t){
	if(t>0) return t-1;
	return 3;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&t[i][j]);
	scanf("%d%d%d%d%s",&sx,&sy,&ex,&ey,c);
	if(c[0]=='S') sd=0;
	else if(c[0]=='N') sd=1;
	else if(c[0]=='E') sd=2;
	else sd=3;
	if(!check2(sx,sy)||!check2(ex,ey)){
		printf("-1");
		return 0;
	}
	put(sx,sy,sd,0);
	vis[sx][sy][sd]=1;
	while(!q.empty()){
		node now=q.front();
		q.pop();
		if(now.x==ex&&now.y==ey){
			printf("%d",now.s);
			return 0;
		}
		int nx=now.x,ny=now.y;
		for(int i=0;i<3;i++){
			nx+=dx[now.d];ny+=dy[now.d];
			if(!check2(nx,ny)) break;
			if(!vis[nx][ny][now.d]){
				vis[nx][ny][now.d]=1;
				put(nx,ny,now.d,now.s+1);
			}
		}
		if(!vis[now.x][now.y][aa(now.d)]){
			vis[now.x][now.y][aa(now.d)]=1;
			put(now.x,now.y,aa(now.d),now.s+1);
		}
		if(!vis[now.x][now.y][bb(now.d)]){
			vis[now.x][now.y][bb(now.d)]=1;
			put(now.x,now.y,bb(now.d),now.s+1);
		}
	}
	printf("-1");
	return 0;
}
2022/11/5 11:15
加载中...