80分求调,WA #8 #9
查看原帖
80分求调,WA #8 #9
754444
tamamocross楼主2023/7/8 17:54
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
struct ele{
	int x,y,tow,d;
	ele(int x_,int y_,int tow_,int d_){
		x=x_;y=y_;tow=tow_,d=d_;
	}
};
queue<ele> q;
int n,m;
map <char,int> mp;
const int Max=51;
const int INF=0x3f3f3f3f;
int a[Max][Max];
int x1,y1,x2,y2;
int dis[Max][Max][4];
int mx[4]={-1,0,1,0},my[4]={0,1,0,-1};
void init(){
	mp.insert(make_pair('N',0));
	mp.insert(make_pair('W',1));
	mp.insert(make_pair('S',2));
	mp.insert(make_pair('E',3));
} 
int bfs(){
	while(q.size()){
		ele f=q.front();q.pop();
		int x=f.x,y=f.y,tow=f.tow,d=f.d;
		if(x==x2&&y==y2){
			dis[x][y][tow]=d;
			return d;
		}
		if(x>0&&x<=n&&y>0&&y<=m&&dis[x][y][tow]==INF){
			dis[x][y][tow]=d;
			if(!a[x+1*mx[tow]][y+1*my[tow]]){
				ele tmp1(x+1*mx[tow],y+1*my[tow],tow,d+1);q.push(tmp1);
				if(!a[x+2*mx[tow]][y+2*my[tow]]){
					ele tmp2(x+2*mx[tow],y+2*my[tow],tow,d+1);q.push(tmp2);
					if(!a[x+3*mx[tow]][y+3*my[tow]]){
						ele tmp3(x+3*mx[tow],y+3*my[tow],tow,d+1);q.push(tmp3);
					}
				}
			}
			ele tmp4(x,y,(tow+1)%4,d+1);q.push(tmp4);
			ele tmp5(x,y,(tow+3)%4,d+1);q.push(tmp5);
		}	
	}
	return -1;
}
int main(){
	init();
	cin>>n>>m;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			bool tmp;
			cin>>tmp;
			if(tmp){
				a[i][j]=1;a[i][j-1]=1;a[i-1][j]=1;a[i-1][j-1]=1;
			}
		}
	}	
	cin>>x1>>y1>>x2>>y2;
	if(a[x2][y2]){
		cout<<-1;
		return 0;
	}
	char tow;
	cin>>tow;
	ele tmp(x1,y1,mp[tow],0);
	q.push(tmp);
	cout<<bfs();
} 
2023/7/8 17:54
加载中...