问题存放站
2026-07-15 20:45:58
发布于：浙江
1阅读
0回复
0点赞
1.https://xinyoudui.com/ac/contest/745010F75000BED091A8B1/problem/45749 冰场折返
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define int long long
struct Node{
int x,y,b;
}node[N],node1[N];
int A[N],B[N];
bool cmp(Node a,Node b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
bool cmp1(Node a,Node b){
if(a.y!=b.y)return a.y<b.y;
return a.x<b.x;
}
struct Nodeq{
int nx,ny,now;
int f;//方向
};
queue<Nodeq>q;
bool vis[N][5][5];//每个路障，从四个方向过来，再从四个方向划出
signed main(){
int h,w,n;//行数，列数，路障数
cin>>h>>w>>n;
int sx,sy,gx,gy;//起点，终点
cin>>sx>>sy>>gx>>gy;
for(int i=1;i<=n;i++)cin>>node[i].x>>node[i].y,node[i].b=i;
for(int i=1;i<=n;i++)node1[i]=node[i];
sort(node+1,node+1+n,cmp);
sort(node1+1,node1+1+n,cmp1);
for(int i=1;i<=n;i++)A[i]=node[i].x,B[i]=node1[i].y;
q.push({sx,sy,0,1});//上
q.push({sx,sy,0,2});//下
q.push({sx,sy,0,3});//左
q.push({sx,sy,0,4});//右
while(!q.empty()){
Nodeq sum=q.front();
q.pop();
if(sum.nx==gx&&sum.ny==gy){
cout<<sum.now;
return 0;
}
if(sum.f==1){
int su=lower_bound(B+1,B+1+n,sum.ny)-B;
if(B[su]!=sum.ny||su==n+1)continue;
while(B[su]==sum.ny&&node1[su].x<sum.nx)su++;
su--;
if(node1[su].x>=sum.nx)continue;
for(int i=1;i<=4;i++){
if(vis[node1[su].b][2][i])continue;
if(i==2)continue;
vis[node1[su].b][2][i]=1;
q.push({node1[su].x+1,node1[su].y,sum.now+1,i});
}
}else if(sum.f==2){
int su=lower_bound(B+1,B+1+n,sum.ny)-B;
if(B[su]!=sum.ny||su==n+1)continue;
while(B[su]==sum.ny){
if(node1[su].x>sum.nx)break;
su++;
}
if(node1[su].x<=sum.nx)continue;
for(int i=1;i<=4;i++){
if(vis[node1[su].b][1][i])continue;
if(i==1)continue;
vis[node1[su].b][1][i]=1;
q.push({node1[su].x-1,node1[su].y,sum.now+1,i});
}
}else if(sum.f==3){
int su=lower_bound(A+1,A+1+n,sum.nx)-A;
if(A[su]!=sum.nx||su==n+1)continue;
while(A[su]==sum.nx&&node[su].y<sum.ny)su++;
su--;
if(node[su].y>=sum.ny)continue;
for(int i=1;i<=4;i++){
if(vis[node[su].b][4][i])continue;
if(i==4)continue;
vis[node[su].b][4][i]=1;
q.push({node[su].x,node[su].y+1,sum.now+1,i});
}
}else if(sum.f==4){
int su=lower_bound(A+1,A+1+n,sum.nx)-A;
if(A[su]!=sum.nx||su==n+1)continue;
while(A[su]==sum.nx){
if(node[su].y>sum.ny)break;
su++;
}
if(node[su].y<=sum.ny)continue;
for(int i=1;i<=4;i++){
if(vis[node[su].b][3][i])continue;
if(i==3)continue;
vis[node[su].b][3][i]=1;
q.push({node[su].x,node[su].y-1,sum.now+1,i});
}
}
}
cout<<-1;
return 0;
}
为什么加上四个if就可以通过？
这里空空如也
有帮助，赞一个