好题啊好题!
一个10*10的房间里,有n堵墙。每堵墙有两扇门,求最短路经
先枚举门的端点,在判断端点连线是否有与其他墙相交,构图,最后dij求最短路!思路一定要清晰。
最后,这题的数组最好开大点。不要天真的以为它只有9堵墙。。它有18堵啊有木有!!
//Memory: 528K //Time: 0MS #include <iostream> #include <string.h> #include <math.h> #define inf 100 using namespace std; double map[200][200]; bool vist[200]; double dis[200]; int n; struct POINT {double x,y; };POINT p[200]; struct LINESEG { POINT s,e; };LINESEG l[200]; void init() { memset(map,0,sizeof(map)); memset(vist,0,sizeof(vist)); } double dist(POINT p1,POINT p2) { return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) ); } double multiply(POINT sp,POINT ep,POINT op) { return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); } bool intersect_l(LINESEG u,LINESEG v) //线段u跨立v所在直线 { return multiply(u.s,v.e,v.s)*multiply(v.e,u.e,v.s)>=0; } void getmap() { int i,j; LINESEG temp; bool flag; for(i=0;i<n;i++) { for(j=(i+3)/4*4+1;j<=n;j++) { flag=true; temp.s=p[i]; temp.e=p[j]; for(int c=(i+3)/4+1;c<(j+3)/4;c++) { for(int d=1;d<=3;d++) if(intersect_l(l[3*(c-1)+d],temp)) //与两点之间的墙判别是否相交,相交则两点间不可达 { flag=false; break; } if(!flag) break; } if(flag) map[i][j]=dist(temp.s,temp.e); } } } double dijkstra() { int node,i,j; double mindist; for(i=1;i<=n;i++) { if(map[0][i]!=0) dis[i]=map[0][i]; else dis[i]=inf; } for(i=0;i<=n;i++) { node=0; mindist=inf; for(j=1;j<=n;j++) if(!vist[j] && mindist>dis[j]) { mindist=dis[j]; node=j; } if(node==0) break; vist[node]=true; for(j=0;j<=n;j++) if(!vist[j] && map[node][j]>0 && dis[j]>dis[node]+map[node][j]) dis[j]=dis[node]+map[node][j]; } return dis[n]; } int main() { while(cin>>n) { if(n==-1) break; init(); int i,j=1,k=1; double ans; for(i=1;i<=n;i++) { cin>>p[j].x>>p[j].y>>p[j+1].y>>p[j+2].y>>p[j+3].y; p[j+3].x=p[j+2].x=p[j+1].x=p[j].x; l[k].s.x=p[j].x;l[k].s.y=0.0; l[k].e=p[j]; l[k+1].s=p[j+1]; l[k+1].e=p[j+2]; l[k+2].s=p[j+3]; l[k+2].e.x=p[j].x;l[k+2].e.y=10.0; j+=4;k+=3; } n=n*4+1; //用n来表示端点的总数 p[0].x=0;p[0].y=5; p[n].x=10;p[n].y=5; getmap(); ans=dijkstra(); printf("%.2lf\n",ans); } return 0; }