题目大意：给定平面上的n个正方形，求某个点到另一个点至少穿过多少个边界
一开始想对于每个正方形判断一下起点和终点是否在同一侧= = 但是反例显然
考虑到n<=100，可以离散化一下，然后用Floodfill标记每块区域
然后跑最短路就行了……由于边权都是1，，所以用BFS就能搞出最短路了
连边连挂了调了半宿……
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 310using namespace std;struct abcd{int x,y,c;friend istream& operator >> (istream &_,abcd &a){scanf("%d%d%d",&a.x,&a.y,&a.c);return _;}}a[M];struct Rectangle{int x1,x2,y1,y2;}rectangles[M];struct edge{int to,next;}table[500500];int head[M*M],tot;int m=1,n=1,cnt,T;int xa,ya,xb,yb,map[M][M],f[100100];pair<int,int*> b[M];bool map1[M][M],map2[M][M];void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void Floodfill(int x,int y){int xx,yy;map[x][y]=T;xx=x,yy=y-1;if( !map1[x][y] ){if( y!=1 && !map[xx][yy] )Floodfill(xx,yy);}else if(map[xx][yy])Add(T,map[xx][yy]),Add(map[xx][yy],T);xx=x,yy=y+1;if( !map1[x][y+1] ){if( y!=n && !map[xx][yy] )Floodfill(xx,yy);}else if(map[xx][yy])Add(T,map[xx][yy]),Add(map[xx][yy],T);xx=x-1,yy=y;if( !map2[x][y] ){if( x!=1 && !map[xx][yy] )Floodfill(xx,yy);}else if(map[xx][yy])Add(T,map[xx][yy]),Add(map[xx][yy],T);xx=x+1,yy=y;if( !map2[x+1][y] ){if( x!=m && !map[xx][yy] )Floodfill(xx,yy);}else if(map[xx][yy])Add(T,map[xx][yy]),Add(map[xx][yy],T);}void BFS(){static int q[65540];static unsigned short r,h;int i;f[q[++r]=map[xa][ya]]=1;while(r!=h){int x=q[++h];for(i=head[x];i;i=table[i].next)if(!f[table[i].to])f[q[++r]=table[i].to]=f[x]+1;}}int main(){int i,j;cin>>cnt;for(i=1;i<=cnt;i++)cin>>a[i];cin>>xa>>ya>>xb>>yb;for(i=1;i<=cnt;i++){b[i+i-1]=make_pair(a[i].x,&rectangles[i].x1);b[i<<1]=make_pair(a[i].x+a[i].c,&rectangles[i].x2);}b[cnt<<1|1]=make_pair(xa,&xa);b[cnt+1<<1]=make_pair(xb,&xb);sort(b+1,b+(cnt+1<<1)+1);for(i=1;i<=(cnt+1<<1);i++){if(i==1||b[i].first!=b[i-1].first)++m;*b[i].second=m;}m+=2;for(i=1;i<=cnt;i++){b[i+i-1]=make_pair(a[i].y,&rectangles[i].y1);b[i<<1]=make_pair(a[i].y+a[i].c,&rectangles[i].y2);}b[cnt<<1|1]=make_pair(ya,&ya);b[cnt+1<<1]=make_pair(yb,&yb);sort(b+1,b+(cnt+1<<1)+1);for(i=1;i<=(cnt+1<<1);i++){if(i==1||b[i].first!=b[i-1].first)++n;*b[i].second=n;}n+=2;for(i=1;i<=cnt;i++){for(j=rectangles[i].x1;j<rectangles[i].x2;j++)map1[j][rectangles[i].y1]=map1[j][rectangles[i].y2]=true;for(j=rectangles[i].y1;j<rectangles[i].y2;j++)map2[rectangles[i].x1][j]=map2[rectangles[i].x2][j]=true;}for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(!map[i][j])++T,Floodfill(i,j);BFS();cout<<f[map[xb][yb]]-1<<endl;return 0;}
灯红酒绿的城市，登上楼顶，俯视万家灯火，
