题解 P2537 【[AHOI2005]穿越磁场】

· · 题解

有一个简单的想法。直接判断两个点所属的不同的矩形的数量。

最开始一直不知道问题出在哪儿，后来借鉴了题解的图。

可以看出，题目的坑点在于无法沿边线走。

正解：我们可以通过数据发现，n非常小，只有100。那么我们先离散化。然后在离散化后的图中在两点之间连边。没有跨过磁场的边权为0，跨过磁场的边权为1。然后跑spfa就可以了。

不过离散化的时候需要注意一些小问题。不能直接把第一个出现和最后一个出现的横坐标和纵坐标看成是边界，因为磁场是没有边界的，它有可能从外面绕一大圈过去，并不穿过磁场。 还有就是要注意离散化的时候不要把一些能通过的地方变成不能通过的了，比如说本来两条边中间有路可走结果处理成了两条边相邻，也不能把原来不能走的地方处理成能走的了。

code

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 510
using namespace std;

struct node{
    int a,b,c,d;
}s[maxn];

int n,x,y,l,A,B,C,D;
int xx,yy,cntx,cnty,X[maxn*2],Y[maxn*2],xp[maxn*2],yp[maxn*2],lshx[maxn*2],lshy[maxn*2];
int tot,point[maxn*maxn],nxt[maxn*maxn*10],v[maxn*maxn*10],c[maxn*maxn*10],dis[maxn*maxn];
bool flag[maxn][maxn][2],vis[maxn*maxn];
queue<int> q;

int cmpx(int x,int y){
    return X[x]<X[y];
}

int cmpy(int x,int y){
    return Y[x]<Y[y];
}

void add(int x,int y,int z){
    nxt[++tot]=point[x];point[x]=tot;v[tot]=y;c[tot]=z;
    nxt[++tot]=point[y];point[y]=tot;v[tot]=x;c[tot]=z;
}

void spfa(){
    int s=(A-1)*cnty+B;
    memset(dis,127,sizeof(dis)),dis[s]=0;
    memset(vis,0,sizeof(vis)),vis[s]=true;
    while(!q.empty()) q.pop();
    q.push(s);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=false;
        for(int i=point[now];i;i=nxt[i])
            if(dis[v[i]]>dis[now]+c[i]){
                dis[v[i]]=dis[now]+c[i];
                if(!vis[v[i]]){
                    vis[v[i]]=true;
                    q.push(v[i]);
                }
            }
    }
}

void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d%d",&x,&y,&l);
        X[++xx]=x,xp[xx]=xx,X[++xx]=x+l,xp[xx]=xx;
        Y[++yy]=y,yp[yy]=yy,Y[++yy]=y+l,yp[yy]=yy;
    }
    scanf("%d%d%d%d",&A,&B,&C,&D);
    X[++xx]=A,xp[xx]=xx,X[++xx]=C,xp[xx]=xx;
    Y[++yy]=B,yp[yy]=yy,Y[++yy]=D,yp[yy]=yy;

    X[++xx]=-1,xp[xx]=xx,Y[++yy]=-1,yp[yy]=yy;
    X[++xx]=10000,xp[xx]=xx,Y[++yy]=10000,yp[yy]=yy;
}

void lsh(){
    sort(xp+1,xp+xx+1,cmpx);sort(yp+1,yp+yy+1,cmpy);
    for(int i=1;i<=xx;++i){
        if(X[xp[i]]!=X[xp[i-1]]) ++cntx,lshx[xp[i]]=++cntx;
        else lshx[xp[i]]=cntx;
    }
    for(int i=1;i<=yy;++i){
        if(Y[yp[i]]!=Y[yp[i-1]]) ++cnty,lshy[yp[i]]=++cnty;
        else lshy[yp[i]]=cnty;
    }
    xx=yy=0;
    for(int i=1;i<=n;++i){
        s[i].a=lshx[++xx],s[i].b=lshx[++xx];
        s[i].c=lshy[++yy],s[i].d=lshy[++yy];
    }
    A=lshx[++xx],C=lshx[++xx],B=lshy[++yy],D=lshy[++yy];
}

int main(){
    init();
    lsh();
    for(int i=1;i<=n;++i){
        int a=s[i].a,b=s[i].b,c=s[i].c,d=s[i].d;
        for(int j=a;j<b;++j) flag[j][d][0]=flag[j][c][0]=1;
        for(int j=c;j<d;++j) flag[a][j][1]=flag[b][j][1]=1;
    }
    for(int i=1;i<=cntx;++i)
        for(int j=1;j<=cnty;++j){
            int r=(i-1)*cnty+j,t;
            if(!flag[i][j][0]){
                t=i*cnty+j;
                if(flag[i][j][1]) add(r,t,1);
                else add(r,t,0);
            }
            if(!flag[i][j][1]){
                t=(i-1)*cnty+j+1;
                if(flag[i][j][0]) add(r,t,1);
                else add(r,t,0);
            }
        }
    spfa();
    int t=(C-1)*cnty+D;
    printf("%d\n",dis[t]);
}