40分求助,找许久问题了
查看原帖
40分求助,找许久问题了
963391
Black_Smith楼主2023/11/21 17:56
#include<bits/stdc++.h>
using namespace std;
const int N=55;
map<char,int>mp{{'E',0},{'S',1},{'W',2},{'N',3}};
int n,m,sx,sy,ex,ey;
bool vis[N][N],f[N][N][4];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct E{
	int x,y,step,dir;
};
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			int x;scanf("%d",&x);
			if(x)vis[i][j]=vis[i-1][j]=vis[i][j-1]=vis[i-1][j-1]=true;
		}
	}
	char c;
	scanf("%d %d %d %d %c",&sx,&sy,&ex,&ey,&c);
	queue<E>q;
	q.push({sx,sy,0,mp[c]});
	while(!q.empty()){
		E p=q.front();
		f[p.x][p.y][p.dir]=true;
		if(p.x==ex&&p.y==ey){
			printf("%d",p.step);
			return 0;
		}
		p.step++;
		E t=p;
		for(int i=1;i<=2;++i){
			t.dir=(t.dir+i)%4;
			if(!f[t.x][t.y][t.dir])q.push(t);
		}
		for(int i=0;i<3;++i){
			p.x+=dx[p.dir],p.y+=dy[p.dir];
			if(p.x>=1&&p.x<n&&p.y>=1&&p.y<m&&!vis[p.x][p.y]&&!f[p.x][p.y][p.dir])q.push(p);
			else break;
		}
		q.pop();
	}
	printf("-1");
	return 0;
}
2023/11/21 17:56
加载中...