shortestpathbetweenpoints.cpp

假设有一间房子,在房子丽的任意两点之间铺设电线,要求线要和墙面平行,求最短距离.用了贪婪算法.

                a->z=b->z;
                a->location=b->location;
                b->x=temp->x;
                b->y=temp->y;
                b->z=temp->z;
                b->location=temp->location;
            }

                if(a->location==1||a->location==3)
                    if((doormid->x-B/2)<a->x&&a->x<(doormid->x+B/2)&&(doormid->x-B/2)<b->x&&b->x<(doormid->x+B/2)){ //outlet a and b are both between left side and right side of the wall
                        d1=a->z+b->z+fabs(a->y-b->y)+fabs(a->x-b->x)+cross2(a,b);
                        d2=a->x+b->x+fabs(a->y-b->y)+fabs(a->z-b->z);
                        d3=2*Lx-(a->x+b->x)+fabs(a->y-b->y)+fabs(a->z-b->z);
                    }
                    else if(a->z<H&&b->z<H){    //need to cross the door
                        d1=a->z+b->z+fabs(a->y-b->y)+fabs(a->x-b->x);
                        if(a->x>doormid->x){          //outlet a is at the left of the door
                            d2=a->x+b->x+fabs(a->y-b->y)+fabs(a->z-b->z)+cross1(a,b);
                            d3=2*Lx-(a->x+b->x)+fabs(a->y-b->y)+fabs(a->z-b->z);
                        }
                        else{                          //outlet a is at the right of the door
                            d3=a->x+b->x+fabs(a->y-b->y)+fabs(a->z-b->z);
                            d2=2*Lx-(a->x+b->x)+fabs(a->y-b->y)+fabs(a->z-b->z)+cross1(a,b);
                        }
                     }
                    else{            //need not to cross the door
                        d1=d1=a->z+b->z+fabs(a->y-b->y)+fabs(a->x-b->x);
                        d2=a->x+b->x+fabs(a->y-b->y)+fabs(a->z-b->z);
                        d3=2*Lx-(a->x+b->x)+fabs(a->y-b->y)+fabs(a->z-b->z);
                    }
                if(a->location==2||a->location==4)         //in this case we must chang x to y,but the basic situationg is same
                    if((doormid->y-B/2)<a->y&&a->y<(doormid->x+B/2)&&(doormid->y-B/2)<b->y&&b->y<(doormid->y+B/2)){   //outlet a and b are both between left side and right side of the wall
                        d1=a->z+b->z+fabs(a->y-b->y)+fabs(a->x-b->x)+cross3(a,b);
                        d2=a->y+b->y+fabs(a->x-b->x)+fabs(a->z-b->z);
                        d3=2*Ly-(a->y+b->y)+fabs(a->x-b->x)+fabs(a->z-b->z);
                    }
                    else if(a->z<H&&b->z<H){              //need to cross the door
                        d1=a->z+b->z+fabs(a->y-b->y)+fabs(a->x-b->x);
                        if(a->y>doormid->y){              //outlet a is at the left of the door
                            d2=a->y+b->y+fabs(a->x-b->x)+fabs(a->z-b->z)+cross1(a,b);
                            d3=2*Ly-(a->y+b->y)+fabs(a->x-b->x)+fabs(a->z-b->z);
                        }
                        else{                              //outlet a is at the right of the door
                            d3=a->y+b->y+fabs(a->x-b->x)+fabs(a->z-b->z);
                            d2=2*Ly-(a->y+b->y)+fabs(a->x-b->x)+fabs(a->z-b->z)+cross1(a,b);
                        }
                     }
                    else{                      //need not to cross the door
                        d1=d1=a->z+b->z+fabs(a->y-b->y)+fabs(a->x-b->x);
                        d2=a->y+b->y+fabs(a->x-b->x)+fabs(a->z-b->z);
                        d3=2*Ly-(a->y+b->y)+fabs(a->x-b->x)+fabs(a->z-b->z);
                    }
                    
                distant=min3(d1,d2,d3);
        }
    }
    
    else if(fabs(a->location-b->location)==0){    ////the two outlets are in the same wall
        if(a->location==doormid->location&&a->z<H&&b->z<H&&((doormid->x-a->x)*(doormid->x-b->x)<0||(doormid->y-a->y)*(doormid->y-b->y)<0))    //when the door is in the same wall and two outlets both below the height of the door and they are in the different side of the door,we need cross it
        distant=fabs(a->x-b->x)+fabs(a->y-b->y)+fabs(a->z-b->z)+cross1(a,b);
        else
        distant=fabs(a->x-b->x)+fabs(a->y-b->y)+fabs(a->z-b->z);
     }

    else if(fabs(a->location-b->location)==1||fabs(a->location-b->location)==3){        //the two outlets are in the neighborhood walls
        if((a->location==doormid->location||b->location==doormid->location)&&a->z<H&&b->z<H&&((doormid->x-a->x)*(doormid->x-b->x)<0||(doormid->y-a->y)*(doormid->y-b->y)<0))   //when the door is in the same wall with either outlet and two outlets both below the height of the door and they are in the different side of the door,we need cross it
        distant=distant=fabs(a->x-b->x)+fabs(a->y-b->y)+fabs(a->z-b->z)+cross1(a,b);
        else
        distant=fabs(a->x-b->x)+fabs(a->y-b->y)+fabs(a->z-b->z);
      }
      return distant;
}


float cross1(NOD a,NOD b)
{
    float m,n,d;
    m=a->z<b->z?a->z:b->z;
    n=(H-a->z)<(H-b->z)?(H-a->z):(H-b->z);
    d=m<n?m:n;         //find the minimum extra disdant
    return (d>0?2*d:0);  // solve the bug when it need not cross the door indeed
}


float cross2(NOD a,NOD b)
{
    float m,n,d;
    m=(doormid->x+B/2-a->x)<(doormid->x+B/2-b->x)?(doormid->x+B/2-a->x):(doormid->x+B/2-b->x);
    n=(a->x-(doormid->x-B/2))<(b->x-(doormid->x-B/2))?(a->x-(doormid->x-B/2)):(b->x-(doormid->x-B/2));
    d=m<n?m:n;       //find the minimum extra disdant
    return (d>0?2*d:0);  // solve the bug when it need not cross the door indeed
}

float cross3(NOD a,NOD b)
{
    float m,n,d;
    m=(doormid->y+B/2-a->y)<(doormid->y+B/2-b->y)?(doormid->y+B/2-a->y):(doormid->y+B/2-b->y);
    n=(a->y-(doormid->y-B/2))<(b->y-(doormid->y-B/2))?(a->y-(doormid->y-B/2)):(b->y-(doormid->y-B/2));
    d=m<n?m:n;       //find the minimum extra disdant
    return (d>0?2*d:0);  // solve the bug when it need not cross the door indeed
}
    
float min3(float a,float b,float c)
{
    if(a>b)
    a=b;
    if(a>c)
    a=c;
    return a;               //a is the minimum number int the three ones
}

float kruskal(WAY way[],NOD outlet[],int m,int n)
{
    NOD p;
    WAY temp;
    float result=0;
    int i,j;
    int k=1;          //k shows the number of the edge of the minimum spanning tree
    int d=0;           //d shows the numth of the edge in array way[]
    int m1,m2;        //m1 and m2 shows the start and the end of an edge
    WAY loop[20];     //used to store the elected edge

    for(i=1;i<m;i++){               //sort the edge by disdant from min to max
        temp=way[i];
        for(j=i;j>0&&way[j-1]->dis>temp->dis;j--)
            way[j]=way[j-1];
        way[j]=temp;
    }
    
    while(k<n){                    //we need n-1 edges
        for(i=0;i<n;i++){
            p=outlet[i];
            while(p!=NULL){         //find the start and end of the edge
                if(p->num==way[d]->a->num)
                m1=i;
                if(p->num==way[d]->b->num)
                m2=i;
                p=p->next;
            }
        }
        
        if(m1!=m2){                  //if the start outlet and end outlet in different set ,we put the edge into array loop[]
            loop[k-1]=way[d];
            k++;
            p=outlet[m1];
            while(p->next!=NULL)       //combine the two sets
            p=p->next;
            p->next=outlet[m2];
            outlet[m2]=NULL;            //make the other set empty
        }
        d++;                            //go to next edge in arry way[]
    }
    
    for(i=0;i<n-1;i++)
    result+=loop[i]->dis;               //compute the result
    
    return result;
}

int up(float x)
{
    if((float)(int)x==x)
    return (int)x;
    else
    return ((int)x+1);     //the celling function
}

void doorcenter(NOD door[])
{
   int j;
   
   doormid=(NOD)malloc(sizeof(struct nod));   //creat a struct
   doormid->x=0;                              //initialize x
   doormid->y=0;                              //initialize y
   doormid->z=0;                              //initialize z

    for(j=0;j<4;j++){
        doormid->x+=door[j]->x;                //compute the sum of the door's four corners
        doormid->y+=door[j]->y;
        doormid->z+=door[j]->z;
    }
    doormid->x/=4;
    doormid->y/=4;
    doormid->z/=4;
    doormid->location=locate(doormid);
    H=2*fabs(doormid->z-door[1]->z);                             //compute the height of the door
    if(doormid->location==1||doormid->location==3)     //compute the breadth of the door
        B=2*fabs(door[1]->x-doormid->x);
    else
        B=2*fabs(door[1]->y-doormid->y);
}