bzoj 1967: [Ahoi2005]CROSS 穿越磁场

.

题意：平面上有n个正方形，问从起点走到终点最少经过几个边界。
题解：离散化后spfa
代码：

#include<bits/stdc++.h>
#define pa pair<int,int>
using namespace std;

int n,sx,sy,tx,ty,maxx,minx,maxy,miny,id[300][300],px[4]={1,0,-1,0},py[4]={0,1,0,-1},fst[900],num=0;
map<int,int>lshx,lshy;
struct rect
{
    int x1,y1,x2,y2;
}a[110];
struct edge
{
    int x,y,n;
}e[810000];
bool mp[300][300],mpp[900][900];

void ins(int x,int y)
{
    e[++num]={x,y,fst[x]};
    fst[x]=num;
}
inline int spfa(pa s,pa t)
{
    static queue<pa>q;
    static map<pa,bool>v;
    static map<pa,int>dis;
    v[s]=1;
    q.push(s);
    dis[s]=0;
    while(!q.empty())
    {
        pa x=q.front();
        v[x]=0;
        for(int i=0;i<4;i++)
        {
            pa y;
            y.first=x.first+px[i];
            y.second=x.second+py[i];
            if(y.first>minx&&y.first<maxx&&y.second>miny&&y.second<maxy&&(dis.count(y)==0||dis[y]>dis[x]+mp[y.first][y.second]))
            {
                dis[y]=dis[x]+mp[y.first][y.second];
                if(!v[y])
                {
                    v[y]=1;
                    q.push(y);
                }
            }
        }
        q.pop();
    }
    return dis[t];
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int c;
        scanf("%d%d%d",&a[i].x1,&a[i].y1,&c);
        a[i].x2=a[i].x1+c;
        a[i].y2=a[i].y1+c;
        lshx[a[i].x1]=lshx[a[i].x2]=lshy[a[i].y1]=lshy[a[i].y2]=1;
    }
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    lshx[sx]=lshx[tx]=lshy[sy]=lshy[ty]=1;
    int last=0,nn=2;
    for(map<int,int>::iterator it=lshx.begin();it!=lshx.end();it++)
    {
        if(it->first-last>1)
        nn+=2;
        else
        nn++;
        it->second=nn;
        last=it->first;
    }
    last=0,nn=2;
    for(map<int,int>::iterator it=lshy.begin();it!=lshy.end();it++)
    {
        if(it->first-last>1)
        nn+=2;
        else
        nn++;
        it->second=nn;
        last=it->first;
    }
    maxx=lshx.rbegin()->second+2;
    minx=lshx.begin()->second-2;
    maxy=lshy.rbegin()->second+2;
    miny=lshy.begin()->second-2;
    memset(mp,0,sizeof(mp));
    for(int i=0;i<n;i++)
    {
        a[i].x1=lshx[a[i].x1];
        a[i].y1=lshy[a[i].y1];
        a[i].x2=lshx[a[i].x2];
        a[i].y2=lshy[a[i].y2];
        for(int j=a[i].x1;j<=a[i].x2;j++)
        mp[j][a[i].y1]=mp[j][a[i].y2]=1;
        for(int j=a[i].y1;j<=a[i].y2;j++)
        mp[a[i].x1][j]=mp[a[i].x2][j]=1;
    }
    sx=lshx[sx];
    sy=lshy[sy];
    tx=lshx[tx];
    ty=lshy[ty];
    nn=0;
    for(int i=minx;i<=maxx;i++)
    {
        mp[i][miny]=mp[i][maxy]=1;
    }
    for(int i=miny;i<=maxy;i++)
    {
        mp[minx][i]=mp[maxx][i]=1;
    }
    printf("%d",spfa(make_pair(sx,sy),make_pair(tx,ty)));
}