80分求助
查看原帖
80分求助
1278786
lihaoyyy楼主2024/8/3 17:51

WA第一二点,求助。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5000;
int n,xs,xe,ys,ye;
struct icemountain{
	int xl,yl,xr,yr;
}im[N];
typedef pair<int,int> gr;
queue<gr>q;
map<gr,int>v;
void bfs(){
	q.push({xs,ys});
	v[{xs,ys}]=1;
	while(q.size()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		//处理四面距离冰块的最小值 
		//cout<<x<<" "<<y<<endl;
		int left=-999999999;
		int right=0x7fffffff;
		int on=-999999999;
		int under=0x7fffffff;
		for(int i=1;i<=n;i++){
			int lx=im[i].xl;
			int ly=im[i].yl;
			int rx=im[i].xr;
			int ry=im[i].yr;
			if(lx<=x&&rx>=x&&y<ry)under=min(under,ry);
			if(lx<=x&&rx>=x&&y>ly)on=max(on,ly);
			if(ry>=y&&ly<=y&&x>rx)left=max(left,rx);
			if(ry>=y&&ly<=y&&x<lx)right=min(right,lx);
		}
//cout<<under<<" "<<on<<" "<<left<<" "<<right<<endl;
		//向左推
//		cout<<x<<endl;
		if(y==ye&&x>xe&&left<xe){cout<<v[{x,y}]; exit(0);}
		if(left!=-999999999&&v[{left+1,y}]==0){
		//	v[left+1][y]=v[x][y]+1;
			v[{left+1,y}]=v[{x,y}]+1;
			q.push({left+1,y});
//cout<<num<<" "<<"left: "<<left+1<<" "<<y<<endl;
		}
//		cout<<x<<endl;
		//向右推
		if(y==ye&&x<xe&&right>xe){cout<<v[{x,y}]; exit(0);} 
		if(right!=0x7fffffff&&v[{right-1,y}]==0){
			v[{right-1,y}]=v[{x,y}]+1;
			q.push({right-1,y});
//cout<<num<<" "<<"right: "<<right-1<<" "<<y<<endl;
		}
//		cout<<x<<endl;
		//向上推
		if(x==xe&&y>ye&&on<ye){cout<<v[{x,y}]; exit(0);} 
		if(on!=-999999999&&v[{x,on+1}]==0){
			v[{x,on+1}]=v[{x,y}]+1;
			q.push({x,on+1});
//cout<<num<<" "<<"on: "<<x<<" "<<on+1<<endl;            
		}
	//	cout<<x<<endl;
		//向下推
		if(x==xe&&y<ye&&under>ye){cout<<v[{x,y}]; exit(0);}
		if(under!=0x7fffffff&&v[{x,under-1}]==0){
			v[{x,under-1}]=v[{x,y}]+1;
			q.push({x,under-1});
//cout<<num<<" "<<"under: "<<x<<" "<<under-1<<endl;
		}
	//	cout<<x<<endl;
	}
//cout<<"opps"<<endl;
	cout<<0;
	return ;
}
signed main(){
	cin>>n>>xs>>ys>>xe>>ye;
	for(int i=1;i<=n;i++)cin>>im[i].xl>>im[i].yl>>im[i].xr>>im[i].yr;
//	for(int i=1;i<=1005;i++)for(int j=1;j<=1005;j++)v[i][j]=-1;
	
	bfs();
	return 0;
}
2024/8/3 17:51
加载中...