学步园

我艹，好水啊！！才110行

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
    int lx,ly;
    int rx,ry;
}rec[55];
struct point
{
    int x,y;
    int dis;
};
int hx[555],hy[555];
int n,m;
int sj,si,ei,ej;
int map[555][555];
int vis[555][555];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int getx(int x)
{
    for(int i=1;i<=n;i++)
        if(hx[i]==x) return i;
}
int gety(int y)
{
    for(int i=1;i<=m;i++)
        if(hy[i]==y) return i;
}
bool isok(int x,int y)
{
    return x>=0&&x<=3*n&&y>=0&&y<=3*m;
}
void bfs()
{
    queue<point>  Q;
    point tmp;
    tmp.dis=-1;
    memset(vis,0x3f,sizeof(vis));
    for(int i=si*3;i>=si*3-2;i--)
        for(int j=sj*3;j>=sj*3-2;j--)
            if(map[i][j]==2)
            {
                tmp.x=i;tmp.y=j;
                vis[i][j]=0;
                Q.push(tmp);
            }
    point tt;
    while(!Q.empty())
    {
        tmp=Q.front();
        Q.pop();
        for(int d=0;d<4;d++)
        {
            tt=tmp;tt.dis++;
            tt.x+=dx[d];tt.y+=dy[d];
            while(isok(tt.x,tt.y)&&map[tt.x][tt.y]!=1)
            {
                if(tt.dis<vis[tt.x][tt.y])
                {
                    if(map[tt.x][tt.y]==3) {printf("%d\n",tt.dis);return;}
                    vis[tt.x][tt.y]=tt.dis;
                    Q.push(tt);
                }
                tt.x+=dx[d];tt.y+=dy[d];
            }
        }
    }printf("-1\n");
}
int main()
{
    int sx,sy,ex,ey,T,j;
    while(scanf("%d%d%d%d",&sx,&sy,&ex,&ey))
    {
        if(!sx&&!sy&&!ex&&!ey) break;
        j=3;
        hx[1]=sx,hy[1]=sy;
        hx[2]=ex,hy[2]=ey;
        scanf("%d",&T);
        for(int i=1;i<=T;i++)
        {
            scanf("%d%d%d%d",&rec[i].lx,&rec[i].ly,&rec[i].rx,&rec[i].ry);
            if(rec[i].lx>rec[i].rx) {swap(rec[i].lx,rec[i].rx);swap(rec[i].ly,rec[i].ry);}
            hx[j]=rec[i].lx;hy[j++]=rec[i].ly;hx[j]=rec[i].rx;hy[j++]=rec[i].ry;
        }sort(hx+1,hx+j);sort(hy+1,hy+j);
        n=m=2;
        for(int i=2;i<j;i++) if(hx[i]!=hx[i-1]) hx[n++]=hx[i];n--;
        for(int i=2;i<j;i++) if(hy[i]!=hy[i-1]) hy[m++]=hy[i];m--;
        memset(map,0,sizeof(map));
        si=getx(sx),sj=gety(sy);
        ei=getx(ex),ej=gety(ey);
        for(int i=si*3;i>=si*3-2;i--) for( j=sj*3;j>=sj*3-2;j--) map[i][j]=2;
        for(int i=ei*3;i>=ei*3-2;i--) for(j=ej*3;j>=ej*3-2;j--) map[i][j]=3;
        for(int i=1;i<=T;i++)
        {
            int x1=getx(rec[i].lx),y1=gety(rec[i].ly);
            int x2=getx(rec[i].rx),y2=gety(rec[i].ry);
            for(int i=x1*3;i<=x2*3-2;i++) for( j=y1*3;j<=y2*3-2;j++) map[i][j]=1;
        }
        for(int i=1;i<=n;i++) for( j=1;j<=m;j++)
            {
                if(map[i*3-2][j*3-2]==1&&map[i*3][j*3]==1||map[i*3-2][j*3]==1&&map[i*3][j*3-2]==1) map[i*3-1][j*3-1]=1;
                if(map[i*3-1][j*3-2]==1&&map[i*3-1][j*3]==1) map[i*3-1][j*3-1]=1;
                if(map[i*3-2][j*3-1]==1&&map[i*3][j*3-1]==1) map[i*3-1][j*3-1]=1;
            }bfs();
     }
    return 0;
}