点击这里查看原题
首先可以想到这题求最短路，那肯定是SPFA（没有负权边，Dijkstra当然也可以啦），难点在于如何构图。 将坐标离散化，然后将矩形的边和顶点分别做不同的标记。从每个矩形的四个顶点出发，将到达的第一个有标记的点（也就是其他矩形上的点）标记为mark[i][j]=1。 将所有mark[i][j]=1或是矩形的四个顶点的点加入，在同一行或同一列的点之间连边，然后做SPFA即可。 因为题目保证了数据的合法性，因此不需要特判非法情况（比如起点或终点在矩形内、矩形相互包含等）
/* User:Small Language:C++ Problem No.:2304 */ #include<bits/stdc++.h> #define ll long long using namespace std; const int M=1e3+5; int n,xs,ys,xt,yt,a[M],b[M],c[M],d[M],x[M<<1],y[M<<1],cntx,cnty,cnt,tot,squ[M<<1][M<<1],fir[24005],s,t; bool vis[24005],mark[M<<1][M<<1]; ll dis[24005],inf; struct edge{ int v,w,nex; }e[200005]; struct po{ int x,y,id; }p[24005]; bool cmpx(po a,po b){ return a.x!=b.x?a.x<b.x:a.y<b.y; } bool cmpy(po a,po b){ return a.y!=b.y?a.y<b.y:a.x<b.x; } void init(){ memset(fir,0,sizeof(fir)); memset(mark,0,sizeof(mark)); memset(squ,0,sizeof(squ)); cnt=tot=cntx=cnty=0; } void add(int u,int v,int w){ e[++tot]=(edge){v,w,fir[u]}; fir[u]=tot; e[++tot]=(edge){u,w,fir[v]}; fir[v]=tot; } void walk(int x,int y,int dx,int dy){ x+=dx; y+=dy; while(!squ[x][y]){ if(x<1||x>cntx||y<1||y>cnty) return; x+=dx; y+=dy; } mark[x][y]=1; } int getdis(po &a,po &b){ return abs(x[a.x]-x[b.x])+abs(y[a.y]-y[b.y]); } void spfa(){ queue<int> q; memset(dis,127,sizeof(dis)); inf=dis[0]; dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=fir[u];i;i=e[i].nex){ int v=e[i].v; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; if(!vis[v]){ vis[v]=1; q.push(v); } } } } } void solve(){ init(); scanf("%d%d%d%d",&xs,&ys,&xt,&yt); scanf("%d",&n); x[++cntx]=xs; x[++cntx]=xt; y[++cnty]=ys; y[++cnty]=yt; for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]); if(a[i]>c[i]) swap(a[i],c[i]); if(b[i]>d[i]) swap(b[i],d[i]); x[++cntx]=a[i]; x[++cntx]=c[i]; y[++cnty]=b[i]; y[++cnty]=d[i]; } sort(x+1,x+cntx+1); sort(y+1,y+cnty+1); cntx=unique(x+1,x+cntx+1)-x-1; cnty=unique(y+1,y+cnty+1)-y-1; xs=lower_bound(x+1,x+cntx+1,xs)-x; xt=lower_bound(x+1,x+cntx+1,xt)-x; ys=lower_bound(y+1,y+cnty+1,ys)-y; yt=lower_bound(y+1,y+cnty+1,yt)-y; squ[xs][ys]=squ[xt][yt]=-1;//-1表示是顶点 for(int i=1;i<=n;i++){ a[i]=lower_bound(x+1,x+cntx+1,a[i])-x; c[i]=lower_bound(x+1,x+cntx+1,c[i])-x; b[i]=lower_bound(y+1,y+cnty+1,b[i])-y; d[i]=lower_bound(y+1,y+cnty+1,d[i])-y; for(int j=a[i];j<=c[i];j++) squ[j][b[i]]=1,squ[j][d[i]]=2;//1是左边或上边，2是右边或下边 for(int j=b[i];j<=d[i];j++) squ[a[i]][j]=1,squ[c[i]][j]=2; squ[a[i]][b[i]]=squ[a[i]][d[i]]=squ[c[i]][b[i]]=squ[c[i]][d[i]]=-1; } for(int i=1;i<=n;i++){//扩展可以走到的点 mark[a[i]][b[i]]=mark[a[i]][d[i]]=mark[c[i]][b[i]]=mark[c[i]][d[i]]=1; walk(a[i],b[i],0,-1);walk(a[i],b[i],-1,0); walk(a[i],d[i],-1,0);walk(a[i],d[i],0,1); walk(c[i],b[i],0,-1);walk(c[i],b[i],1,0); walk(c[i],d[i],0,1);walk(c[i],d[i],1,0); } mark[xs][ys]=mark[xt][yt]=1; walk(xs,ys,0,1);walk(xs,ys,0,-1);walk(xs,ys,1,0);walk(xs,ys,-1,0); walk(xt,yt,0,1);walk(xt,yt,0,-1);walk(xt,yt,1,0);walk(xt,yt,-1,0); for(int i=1;i<=cntx;i++){ for(int j=1;j<=cnty;j++){ if(!mark[i][j]) continue; p[++cnt]=(po){i,j,cnt}; if(i==xs&&j==ys) s=cnt; if(i==xt&&j==yt) t=cnt; } } sort(p+1,p+cnt+1,cmpx); for(int i=1,j;i<=cnt;i=j){ j=i+1; while(j<=cnt&&p[i].x==p[j].x){//在x值相同的点之间建边，其中必须至少一个点是顶点或者上一个点是下边 if(squ[p[j-1].x][p[j-1].y]==-1||squ[p[j].x][p[j].y]==-1||squ[p[j-1].x][p[j-1].y]>=squ[p[j].x][p[j].y]) add(p[j-1].id,p[j].id,getdis(p[j-1],p[j])); j++; } } sort(p+1,p+cnt+1,cmpy); for(int i=1,j;i<=cnt;i=j){ j=i+1; while(j<=cnt&&p[i].y==p[j].y){ if(squ[p[j-1].x][p[j-1].y]==-1||squ[p[j].x][p[j].y]==-1||squ[p[j-1].x][p[j-1].y]>=squ[p[j].x][p[j].y]) add(p[j-1].id,p[j].id,getdis(p[j-1],p[j])); j++; } } spfa(); if(dis[t]>=inf) printf("No Path\n"); else printf("%lld\n",dis[t]); } int main(){ freopen("data.in","r",stdin);// int kas; scanf("%d",&kas); while(kas--) solve(); return 0; }