题意

自己看

题解

大水题

你就离散化一下
然后随便跑一下最短路就好了
于是我做了一个早上QAQ

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=211000;
struct qq
{int x1,y1;int x2,y2;int x3,y3;int x4,y4;
}s[N];//一个矩阵的四个坐标 
int n;
int a[N],cnt,cntt;
int id[N];//这个坐标其实是多少
int xcnt,ycnt;//两个的最大边界 
int find (int x)
{int l=1,r=cnt;while (l<=r){int mid=(l+r)>>1;if (a[mid]==x) return id[mid];else if (a[mid]>x) r=mid-1;else l=mid+1;}
}
int tx,ty,px,py;
int P (int x,int y){
   return (x-1)*ycnt+y;}
void discretization ()
{/*for (int u=1;u<=n;u++){printf("%d %d\n%d %d\n%d %d\n%d %d\n",s[u].x1,s[u].y1,s[u].x2,s[u].y2,s[u].x3,s[u].y3,s[u].x4,s[u].y4);printf("\n");}*//*先离散x坐标*/
// printf("YES:%d %d %d %d\n",tx,ty,px,py);cnt=0;for (int u=1;u<=n;u++){a[++cnt]=s[u].x1;a[++cnt]=s[u].x2;a[++cnt]=s[u].x3;a[++cnt]=s[u].x4;}a[++cnt]=tx;a[++cnt]=px;sort(a+1,a+1+cnt);cntt=cnt;cnt=1;for (int u=2;u<=cntt;u++)if (a[u]!=a[cnt])a[++cnt]=a[u];id[1]=2;for (int u=2;u<=cnt;u++)if (a[u]==a[u-1]+1) id[u]=id[u-1]+1;else id[u]=id[u-1]+2;xcnt=id[cnt];for (int u=1;u<=n;u++){s[u].x1=find(s[u].x1);s[u].x2=find(s[u].x2);s[u].x3=find(s[u].x3);s[u].x4=find(s[u].x4);}tx=find(tx);px=find(px);/*先离散x坐标*//*先离散y坐标*/cnt=0;for (int u=1;u<=n;u++){a[++cnt]=s[u].y1;a[++cnt]=s[u].y2;a[++cnt]=s[u].y3;a[++cnt]=s[u].y4;}a[++cnt]=ty;a[++cnt]=py;sort(a+1,a+1+cnt);cntt=cnt;cnt=1;for (int u=2;u<=cntt;u++)if (a[u]!=a[cnt])a[++cnt]=a[u];id[1]=2;for (int u=2;u<=cnt;u++)if (a[u]==a[u-1]+1) id[u]=id[u-1]+1;else id[u]=id[u-1]+2;ycnt=id[cnt];for (int u=1;u<=n;u++){s[u].y1=find(s[u].y1);s[u].y2=find(s[u].y2);s[u].y3=find(s[u].y3);s[u].y4=find(s[u].y4);}   ty=find(ty);py=find(py);
/* printf("YES:%d %d %d %d\n",tx,ty,px,py);/*先离散y坐标*//*for (int u=1;u<=n;u++){printf("%d %d\n%d %d\n%d %d\n%d %d\n",s[u].x1,s[u].y1,s[u].x2,s[u].y2,s[u].x3,s[u].y3,s[u].x4,s[u].y4);printf("\n");}*/
}
bool ok[1005][1005];//这个点是不是磁场上的点struct qt
{int x,y,z,last;
}e[N];int num,last[N];
void init (int x,int y,int z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
void prepare ()
{xcnt++;ycnt++;memset(ok,false,sizeof(ok));//先清为falsefor (int u=1;u<=xcnt;u++)//先把边界处理掉{// printf("YES:%d %d\n",u,1);if (u<xcnt) init(P(u,1),P(u+1,1),0);if(u>1)     init(P(u,1),P(u-1,1),0);if (u<xcnt) init(P(u,ycnt),P(u+1,ycnt),0);if(u>1)     init(P(u,ycnt),P(u-1,ycnt),0);}for (int u=1;u<=ycnt;u++){if (u<ycnt) init(P(1,u),P(1,u+1),0);if (u>1)    init(P(1,u),P(1,u-1),0);if (u<ycnt) init(P(xcnt,u),P(xcnt,u+1),0);if (u>1)    init(P(xcnt,u),P(xcnt,u-1),0);}for (int u=1;u<=n;u++)//我们就把磁场的边也建一下 {for (int i=s[u].y1;i<=s[u].y3;i++){ok[s[u].x1][i]=true;init(P(s[u].x1,i),P(s[u].x1-1,i),1);init(P(s[u].x1,i),P(s[u].x1+1,i),1);ok[s[u].x2][i]=true;init(P(s[u].x2,i),P(s[u].x2-1,i),1);init(P(s[u].x2,i),P(s[u].x2+1,i),1);}for (int i=s[u].x1;i<=s[u].x2;i++){ok[i][s[u].y1]=true;init(P(i,s[u].y1),P(i,s[u].y1-1),1);init(P(i,s[u].y1),P(i,s[u].y1+1),1);ok[i][s[u].y3]=true;init(P(i,s[u].y3),P(i,s[u].y3+1),1);init(P(i,s[u].y3),P(i,s[u].y3-1),1);}}for (int u=2;u<xcnt;u++)for (int i=2;i<ycnt;i++){if(ok[u][i]==false){/* printf("%d %d\n",u,i);system("pause");*/init(P(u,i),P(u-1,i),0);if (!ok[u-1][i])init(P(u-1,i),P(u,i),0);init(P(u,i),P(u+1,i),0);if (!ok[u+1][i])init(P(u+1,i),P(u,i),0);init(P(u,i),P(u,i-1),0);if (!ok[u][i-1])init(P(u,i-1),P(u,i),0);init(P(u,i),P(u,i+1),0);if (!ok[u][i+1])init(P(u,i+1),P(u,i),0);}}
}
int f[N];
queue<int> q;
bool in[N];
void SPFA (int xx)//以这个为起点 
{memset(in,false,sizeof(in));memset(f,127,sizeof(f));q.push(xx);f[xx]=0;in[xx]=true;while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (f[y]>f[x]+e[u].z){f[y]=f[x]+e[u].z;if (in[y]==false){in[y]=true;q.push(y);}}}in[x]=false;}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d",&n);for (int u=1;u<=n;u++){int x,y,c;scanf("%d%d%d",&x,&y,&c);s[u]={x,y,x+c,y,x,y+c,x+c,y+c};}scanf("%d%d%d%d",&tx,&ty,&px,&py);discretization();prepare();SPFA(P(tx,ty));printf("%d\n",f[P(px,py)]);return 0;
}

TKJ大佬的数据生成器:
大家快去感谢帮你们写生成器的人

#include<bits/stdc++.h>
using namespace std;int n=2;
map<int,map<int,int> >tf;bool chk(int x,int y,int c)
{for(int i=0;i<=c;i++){if(tf[x][y+i]||tf[x+i][y]||tf[x+c][y+c-i]||tf[x+c-i][y+c])return 0;}return 1;
}
void wk(int x,int y,int c)
{for(int i=0;i<=c;i++){tf[x][y+i]=tf[x+i][y]=tf[x+c][y+c-i]=tf[x+c-i][y+c]=1;}
}
int main()
{srand(time(0));printf("%d\n",n);for(int i=0;i<n;i++){int x=rand()%10,y=rand()%10,c=rand()%10+1;while(!chk(x,y,c))x=rand()%10,y=rand()%10,c=rand()%10+1;wk(x,y,c);printf("%d %d %d\n",x,y,c);}int sx=rand()%10,sy=rand()%10,tx=rand()%10,ty=rand()%10;while(tf[sx][sy])sx=rand()%10,sy=rand()%10;while(tf[tx][ty])tx=rand()%10,ty=rand()%10;printf("%d %d %d %d",sx,sy,tx,ty);
}