强墙

描述 Description  

       　　在一个长宽均为10，入口出口分别为（0，5）、（10，5）的房间里，有几堵墙，每堵墙上有两个缺口，求入口到出口的最短路经。                                       

输入格式 Input Format

        第一排为n(n<=20)，墙的数目。

 接下来n排，每排5个实数x，a1，b1，a2，b2。

 x表示墙的横坐标（所有墙都是竖直的），a1-b1和a2-b2之间为空缺。

 a1、b1、a2、b2保持递增，x1-xn也是递增的。

输出格式 Output Format    

        输出最短距离，保留2位小数。

#include<iostream>
#include<math.h> 
//#include<fstream> 
#include<stdio.h> 
using namespace std;

double d[25][5],y[25][5],x[25]; 
int n; 

int main()
{
    int i,j,k,l; 
    cin>>n;
    
    for(j=1;j<=4;++j)
    {d[1][j]=0;x[1]=0;y[1][j]=5;} 
    
    for(i=2;i<=n+1;++i)
    {
      cin>>x[i];
      for(j=1;j<=4;++j) 
      cin>>y[i][j],d[i][j]=0xfffffff;
            } 
            
    for(j=1;j<=4;++j)
    {x[n+2]=10;y[n+2][j]=5;d[n+2][j]=0xfffffff;} 
    
    for(i=2;i<=n+2;++i)
    {
      for(j=1;j<=4;++j)
      for(k=1;k<=4;++k) 
      d[i][j]=min(d[i][j],sqrt((x[i]-x[i-1])*(x[i]-x[i-1])+(y[i][j]-y[i-1][k])*(y[i][j]-y[i-1][k]))+d[i-1][k]);
                       } 
    
    int s,t; 
    for(i=3;i<=n+2;++i)
    for(j=1;j<=4;++j)
    for(k=i-2;k>=1;--k)
    for(l=1;l<=4;++l)
    {
      for(t=1;t<=4;++t) 
      d[i][j]=min(d[i][j],sqrt((x[i]-x[i-1])*(x[i]-x[i-1])+(y[i][j]-y[i-1][t])*(y[i][j]-y[i-1][t]))+d[i-1][t]);
      double kik=(y[i][j]-y[k][l]); 
      bool p=0; 
      for(t=k+1;t<=i-1;++t)
      {
        p=0; 
        for(s=1;s<=4;++s,++s)
        {
          double kit=(y[i][j]-y[t][s]);
          double kit2=(y[i][j]-y[t][s+1]);                 
          if(kik*(x[i]-x[t])<=kit*(x[i]-x[k])&&kik*(x[i]-x[t])>=kit2*(x[i]-x[k])) p=1;                  
                           }                      
        if(p==0) break;  
                           } 
      if(p==0) continue; 
      d[i][j]=min(d[i][j],d[k][l]+sqrt((x[i]-x[k])*(x[i]-x[k])+(y[i][j]-y[k][l])*(y[i][j]-y[k][l]))); 
                     } 
    
    printf("%.2lf",d[n+2][1]); 
    cout<<endl; 
    return 0; 
    }