60分求助
查看原帖
60分求助
1034206
lusq楼主2023/11/11 11:43
#include<bits/stdc++.h>
using namespace std;
int a[100][100],mina[100][100][4];
struct Node{
	int x,y,t,w;
};
int main(){
	memset(mina,0x7f,sizeof(mina));
	int n,m,s,x1,y1,x2,y2,minn=0x7f7f7f7f;
	char c;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>s;
			if(s==1){
				a[i][j]=a[i+1][j]=a[i][j+1]=a[i+1][j+1]=1;
			}
		}
	}
	cin>>x1>>y1>>x2>>y2>>c;
	queue<Node>q;
	int w;
	if(c=='E'){
		w=0;
	}else if(c=='S'){
		w=1;
	}else if(c=='W'){
		w=2;
	}else{
		w=3;
	}
	q.push({x1,x2,0,w});
	while(q.size()){
		Node p=q.front();
		q.pop();
		if(p.x==x2 && p.y==y2){
			minn=min(minn,p.t);
			continue;
		}
		if(p.t>=mina[p.x][p.y][p.w]){
			continue;
		}else{
			mina[p.x][p.y][p.w]=p.t;
		}
		if(p.t+1<mina[p.x][p.y][(p.w+3)%4]){
			q.push({p.x,p.y,p.t+1,(p.w+3)%4});
		}
		if(p.t+1<mina[p.x][p.y][(p.w+1)%4]){
			q.push({p.x,p.y,p.t+1,(p.w+1)%4});
		}
		for(int i=1;i<=3;i++){
			if(p.w==0){
				if(p.y+i>=m || a[p.x][p.y+i]){
					break;
				}else{
					if(p.t+1<mina[p.x][p.y+i][p.w]){
						q.push({p.x,p.y+i,p.t+1,p.w});
					}
				}
			}else if(p.w==1){
				if(p.x+i>=n || a[p.x+i][p.y]){
					break;
				}else{
					if(p.t+1<mina[p.x+i][p.y][p.w]){
						q.push({p.x+i,p.y,p.t+1,p.w});
					}
				}
			}else if(p.w==2){
				if(p.y-i<=0 || a[p.x][p.y-i]){
					break;
				}else{
					if(p.t+1<mina[p.x][p.y-i][p.w]){
						q.push({p.x,p.y-i,p.t+1,p.w});
					}
				}
			}else{
				if(p.x-i<=0 || a[p.x-i][p.y]){
					break;
				}else{
					if(p.t+1<mina[p.x-i][p.y][p.w]){
						q.push({p.x-i,p.y,p.t+1,p.w});
					}
				}
			}
		}
	}
	if(minn==0x7f7f7f7f){
		cout<<-1;
	}else{
		cout<<minn;
	}
 	return 0;
}

WA了#5、#8、#9、#10

2023/11/11 11:43
加载中...