题目链接：hdu 4444 Walk
题意：
有n个矩形，现在biaoge要从一个点走到另外一个点上，不能穿过矩形，但可以沿着边走。
问最少需要多少次转弯才能到达。
题解：
由于数据很大，需要离散化一下，然后就是一个bfs，用三维的vis来记录最好的状态。
细节比较多，需要考虑延边走时的拐角方向。
1 #include<bits/stdc++.h> 2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 typedef pair<int,int>P; 6 7 const int N=507,inf=1e9,all=1e8+7; 8 int mp[N][N],st[2],en[2],vis[4][N][N]; 9 int hshx[N],hshy[N],hx_ed,hy_ed; 10 int n,NN,MM,dir[][2]={1,0,0,1,-1,0,0,-1}; 11 vector<int>X,Y; 12 struct SQR 13 { 14 P point[2]; 15 void in(int a,int b,int c,int d) 16 { 17 point[0].first=min(a,c); 18 point[0].second=min(b,d); 19 point[1].first=max(a,c); 20 point[1].second=max(b,d); 21 } 22 void get() 23 { 24 point[0].first=lower_bound(X.begin(),X.end(),point[0].first)-X.begin()+1; 25 point[1].first=lower_bound(X.begin(),X.end(),point[1].first)-X.begin()+1; 26 point[0].second=lower_bound(Y.begin(),Y.end(),point[0].second)-Y.begin()+1; 27 point[1].second=lower_bound(Y.begin(),Y.end(),point[1].second)-Y.begin()+1; 28 } 29 }sqr[100]; 30 31 struct Node 32 { 33 int x,y,turn,d; 34 Node(int a=0,int b=0,int c=0,int d_=0):x(a),y(b),turn(c),d(d_){} 35 }; 36 37 int check(int x,int y,int prex,int prey,int i,int prei) 38 { 39 if(x<1||x>NN||y<1||y>MM)return 0; 40 if(mp[x][y]==1) 41 { 42 if((mp[x][y+1]==2&&mp[x][y-1]==2)|| 43 (mp[x+1][y]==2&&mp[x-1][y]==2))return 0; 44 if((mp[x-1][y-1]==2&&mp[x+1][y+1]==2)) 45 { 46 if(prei==0&&i!=1)return 0; 47 if(prei==3&&i!=2)return 0; 48 if(prei==1&&i!=0)return 0; 49 if(prei==2&&i!=3)return 0; 50 } 51 if((mp[x-1][y+1]==2&&mp[x+1][y-1]==2)) 52 { 53 if(prei==0&&i!=3)return 0; 54 if(prei==3&&i!=0)return 0; 55 if(prei==1&&i!=2)return 0; 56 if(prei==2&&i!=1)return 0; 57 } 58 } 59 60 return 1; 61 } 62 63 int bfs() 64 { 65 queue<Node>Q; 66 F(k,0,3)F(i,0,NN+1)F(j,0,MM+1)vis[k][i][j]=inf; 67 F(k,0,3)vis[k][st[0]][st[1]]=0; 68 Q.push(Node(st[0],st[1],0,-1)); 69 while(!Q.empty()) 70 { 71 Node now=Q.front();Q.pop(); 72 if(now.d!=-1&&now.turn>vis[now.d][now.x][now.y])continue; 73 if(now.x==en[0]&&now.y==en[1])continue; 74 F(i,0,3) 75 { 76 int tx=now.x+dir[i][0],ty=now.y+dir[i][1]; 77 int tturn=now.turn; 78 if(now.d!=-1&&now.d!=i)tturn++; 79 if(!check(now.x,now.y,tx,ty,i,now.d)||vis[i][tx][ty]<=tturn||mp[tx][ty]>1)continue; 80 Q.push(Node(tx,ty,tturn,i)); 81 vis[i][tx][ty]=tturn; 82 } 83 } 84 int ans=inf; 85 F(i,0,3)ans=min(ans,vis[i][en[0]][en[1]]); 86 return ans; 87 } 88 89 int main() 90 { 91 while(scanf("%d%d%d%d",st,st+1,en,en+1),st[0]||st[1]||en[1]||en[0]) 92 { 93 st[0]+=all,st[1]+=all,en[0]+=all,en[1]+=all; 94 st[0]*=2,st[1]*=2,en[0]*=2,en[1]*=2; 95 hshx[hx_ed=1]=st[0];hshx[++hx_ed]=en[0]; 96 hshy[hy_ed=1]=st[1];hshy[++hy_ed]=en[1]; 97 scanf("%d",&n); 98 X.clear(),Y.clear(); 99 F(i,1,n) 100 { 101 int a,b,c,d; 102 scanf("%d%d%d%d",&a,&b,&c,&d); 103 a+=all,b+=all,c+=all,d+=all; 104 a*=2,b*=2,c*=2,d*=2; 105 sqr[i].in(a,b,c,d); 106 hshx[++hx_ed]=a,hshx[++hx_ed]=c; 107 hshy[++hy_ed]=b,hshy[++hy_ed]=d; 108 } 109 sort(hshx+1,hshx+1+hx_ed),hx_ed=unique(hshx+1,hshx+1+hx_ed)-hshx-1; 110 sort(hshy+1,hshy+1+hy_ed),hy_ed=unique(hshy+1,hshy+1+hy_ed)-hshy-1; 111 X.push_back(-inf),X.push_back(hshx[1]); 112 F(i,2,hx_ed) 113 { 114 if(hshx[i]>hshx[i-1]+1)X.push_back(hshx[i-1]+1); 115 X.push_back(hshx[i]); 116 } 117 X.push_back(inf); 118 Y.push_back(-inf),Y.push_back(hshy[1]); 119 F(i,2,hy_ed) 120 { 121 if(hshy[i]>hshy[i-1]+1)Y.push_back(hshy[i-1]+1); 122 Y.push_back(hshy[i]); 123 } 124 Y.push_back(inf); 125 F(i,1,n)sqr[i].get(); 126 st[0]=lower_bound(X.begin(),X.end(),st[0])-X.begin()+1; 127 st[1]=lower_bound(Y.begin(),Y.end(),st[1])-Y.begin()+1; 128 en[0]=lower_bound(X.begin(),X.end(),en[0])-X.begin()+1; 129 en[1]=lower_bound(Y.begin(),Y.end(),en[1])-Y.begin()+1; 130 NN=X.size(),MM=Y.size(); 131 F(i,0,NN+1)F(j,0,MM+1)mp[i][j]=0; 132 F(i,1,n) 133 { 134 int x1=sqr[i].point[0].first,x2=sqr[i].point[1].first; 135 int y1=sqr[i].point[0].second,y2=sqr[i].point[1].second; 136 F(j,x1+1,x2-1)F(k,y1+1,y2-1)mp[j][k]=2; 137 F(j,x1,x2)F(k,y1,y2)if(mp[j][k]==0)mp[j][k]=1; 138 } 139 int ans=bfs(); 140 printf("%d ",ans==inf?-1:ans); 141 } 142 return 0; 143 }