30分样例没过求助大佬
查看原帖
30分样例没过求助大佬
947854
ztyo_zysclown楼主2024/1/10 18:47
#include<bits/stdc++.h>
using namespace std;
struct re{
	int x;
	int y;
	int fang;
	int bu;
};
queue<re> q;
int n,m;
bool pd[55][55][400];
int a[55][55];
int fxy1[5][4]={{0,0,0},{1,2,3},{0,0,0},{-1,-2,-3}};
int fxy2[5][4]={{-1,-2,-3},{0,0,0},{1,2,3},{0,0,0}};
int ans=1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	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]=1){
				a[i+1][j+1]=1;
				a[i+1][j]=1;
				a[i][j+1]=1;
			}
		}
	}
	int xa,ya,xb,yb;
	cin>>xa>>ya>>xb>>yb;
	if(xa==xb&&ya==yb){
		cout<<0;
		return 0;
	}
	char fangxiang;
	cin>>fangxiang;
	int f;
	if(fangxiang=='S') f=1;
	if(fangxiang=='W') f=2;
	if(fangxiang=='N') f=3;
	if(fangxiang=='E') f=4;
	q.push((re){xa,xb,f,0});
	while(!q.empty()){
		re x=q.front();
		q.pop();
		if(x.x==xb&&x.y==yb){
			ans=x.bu;
			break;
		}
		for(int i=0;i<4;i++){
			for(int j=0;j<3;j++){
				int tx=x.x+fxy1[i][j];
				int ty=x.y+fxy2[i][j];
				if(tx>1&&ty>1&&tx<n&&ty<m&&a[tx][ty]!=1&&pd[tx][ty][i]==false){
					if(x.fang==i){
						q.push((re){tx,ty,x.fang,x.bu+1});
					}
					if(abs(x.fang-i)==3||abs(x.fang-i)==1){
						q.push((re){tx,ty,i,x.bu+2});
					}
					if(abs(x.fang-i)==2){
						q.push((re){tx,ty,i,x.bu+3});
					}
					pd[tx][ty][i]=true;
				}
			}
		}
	}
	if(ans!=1e9){
		cout<<ans;
	}
	else{
		cout<<-1;
	}
	return 0;
}

2024/1/10 18:47
加载中...