题意：10*10迷宫，n堵墙，求(0,5)到(10,5)的最短距离
找出墙边缘点和起止点两两之间是否可以直线直接通过（不与其他墙相交）可以的话存图 跑一遍dij
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<vector> using namespace std; const double eps = 1e-8; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; #define mp make_pair #define PII pair<int,double> int n; double d[440]; bool vis[440]; vector<PII>G[440]; struct Point{ double x,y; Point(double x = 0,double y = 0) : x(x),y(y) {} }start,endd; typedef Point Vector; struct NODE{ Point p[4]; }a[110]; int dcmp(double x){//equal ?= 0 if(fabs(x) < eps) return 0; else return x < 0 ? -1:1; } //运算符重载 Vector operator + (Vector A, Vector B){ return Vector(A.x+B.x, A.y+B.y); } Vector operator - (Vector A, Vector B){ return Vector(A.x-B.x, A.y-B.y); } Vector operator * (Vector A, double p){ return Vector(A.x*p, A.y*p); } bool operator == (const Point &a, const Point &b){ return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; } double Cross(Vector A, Vector B){ return A.x*B.y - A.y*B.x; } //P点再P1P2上 叉积==0 bool OnSeg(Point P,Point P1,Point P2){ return dcmp(Cross(P1 - P,P2 - P)) == 0; //&& dcmp(Dot(P1 - P,P2 - P)) <= 0; } //?相交 bool check(Point P1,Point P2,Point P3,Point P4){//原线段&线段 注直线&线段 //端点在线上 非规范相交 if(OnSeg(P1,P3,P4)) return 1; if(OnSeg(P2,P3,P4)) return 1; if(OnSeg(P3,P1,P2)) return 1; if(OnSeg(P4,P1,P2)) return 1; //跨立实验规范相交 double _A = Cross(P1 - P2,P3 - P2); double _B = Cross(P1 - P2,P4 - P2); double _C = Cross(P3 - P4,P1 - P4); double _D = Cross(P3 - P4,P2 - P4); return dcmp(_A) * dcmp(_B) < 0 && dcmp(_C) * dcmp(_D) < 0;//=0重合或平行 } double dis(Point A,Point B){ return sqrt((A.x - B.x)*(A.x -B.x) + (A.y - B.y)*(A.y - B.y)); } bool ok(Point A,Point B,int st,int se){//A-B 在墙st到se间有交点 Point tmp1,tmp2; tmp1.y = 0,tmp2.y = 10; for(int i = st;i <= se; i++){ tmp1.x = a[i].p[0].x; tmp2.x = a[i].p[0].x; if(check(A,B,tmp1,a[i].p[0]) || check(A,B,a[i].p[1],a[i].p[2]) || check(A,B,a[i].p[3],tmp2)) return 1; } return 0; } void dij(int x){ memset(vis,0,sizeof vis); for(int i = 0;i <= n * 4 + 1; i++) d[i] = inf * 1.0; d[x] = 0; while(1){ int v = -1; for(int i = 0;i <= n * 4 + 1; i++){ if(!vis[i] && (v == -1 || d[i] < d[v])) v = i; }//d[v] MIN if(v == -1) break; vis[v] = 1; int len = G[v].size(); for(int i = 0;i < len; i++){ int u = G[v][i].first;//contact point if(vis[u]) continue; d[u] = min(d[u],d[v] + G[v][i].second); } } } int main() { start.x = 0; endd.x = 10; start.y = endd.y = 5; while(~scanf("%d",&n) && n != -1){ for(int i = 1;i <= n; i++){ double X; scanf("%lf %lf %lf %lf %lf",&X,&a[i].p[0].y,&a[i].p[1].y,&a[i].p[2].y,&a[i].p[3].y); a[i].p[0].x = a[i].p[1].x = a[i].p[2].x = a[i].p[3].x = X; } if(n == 0 || !ok(start,endd,1,n)){ printf("%.2lf\n",dis(start,endd)); continue; } for(int i = 0;i <= 4 * n + 1; i++) G[i].clear(); //起点到all的dis for(int i = 1;i <= n; i++){ for(int j = 0;j < 4; j++){ if(!ok(start,a[i].p[j],1,i - 1)){ G[0].push_back(mp((i - 1) * 4 + j + 1,dis(start,a[i].p[j]))); G[(i - 1) * 4 + j + 1].push_back(mp(0,dis(start,a[i].p[j]))); // G[0][(i - 1) * 4 + j + 1] = dis(start,a[i].p[j]); } } } //all到终点 for(int i = 1;i <= n; i++){ for(int j = 0;j < 4; j++){ if(!ok(endd,a[i].p[j],i + 1,n)){ G[(i - 1) * 4 + j + 1].push_back(mp(4 * n + 1,dis(endd,a[i].p[j]))); G[4 * n + 1].push_back(mp((i - 1) * 4 + j + 1,dis(endd,a[i].p[j]))); // G[(i - 1) * 4 + j + 1][4 * n + 1] = dis(endd,a[i].p[j]); } } } //all & all for(int i = 1;i < n; i++){ for(int j = i + 1;j <= n; j++){ for(int ki = 0;ki < 4; ki++){ for(int kj = 0;kj < 4; kj++){ if(!ok(a[i].p[ki],a[j].p[kj],i + 1,j - 1)){ G[(i - 1) * 4 + ki + 1].push_back(mp((j - 1) * 4 + kj + 1,dis(a[i].p[ki],a[j].p[kj]))); G[(j - 1) * 4 + kj + 1].push_back(mp((i - 1) * 4 + ki + 1,dis(a[i].p[ki],a[j].p[kj]))); // G[(i - 1) * 4 + ki + 1][(j - 1) * 4 + kj + 1] = dis(a[i].p[ki],a[j].p[kj]); } } } } } dij(0); printf("%.2lf\n",d[4 * n + 1]); } }
