shortestpathbetweenpoints.cpp

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct nod *NOD;          //define the pointer which point to the struct nod
typedef struct edge *WAY;         //define the pointer which point to the struct edge

struct nod{                       //define the struct nod for outlet and door
    float x;
    float y;
    float z;                      //x,y,z use to receive the coordinate position of the nod
    int location;                 //location use to show which wall the nod in
    int num;                      //num use to show the set which the nod belongs to in Kruskal algorithm
    NOD next;                     //a pointer which point to next nod which in the same set
 };
 
struct edge{                      //define the struct nod for outlet and door
    NOD a;                        //show the start nod of the edge
    NOD b;                        //show the end nod of the edge
    float dis;                    //show the length of the edge
};

float Lx,Ly,Lz;                   //show the maximum of the room
NOD door[4];                      //define the four corners of the door
NOD doormid;                      //define the center of the door ,so that we can't mind the order the door's four corners
float H,B;                        //define the length and breadth of the door


int locate(NOD a);                //the function used to show which wall the nod in
float findway(NOD a,NOD b);       //the function used to show the minimum disdant from outlet a to outlet b
float cross1(NOD a,NOD b);        //the function used to show the extra disdant to cross the door according to Z-axis
float cross2(NOD a,NOD b);        //the function used to show the extra disdant to cross the door according to X-axis
float cross3(NOD a,NOD b);        //the function used to show the extra disdant to cross the door according to Y-axis
float kruskal(WAY way[],NOD outlet[],int m,int n);            //the function used to find the minimum spanning tree
float min3(float a,float b,float c);                          //the function used to find the minimum number in three numbers
int up(float x);                                              //the function used to change a float to a int
void doorcenter(NOD door[]);                                  //the function used to compute the center of the door

int main()
{
    int N,n,i,j,k,m,flag;       //N is the number of the case,n is the number of the outlet,m is the number of edge between every pair of outlets,
                                //the flag is used to show the state of the case,flag=1 means door illegal,flag=2 means outlet illegal,
                                //flag=3 means there is no outlet,flag=0 means all the data is right
    FILE *in,*out;
    NOD outlet[20];
    WAY way[190];           //190=20*19/2
    float result;

    if((in=fopen("input.txt","r"))==NULL)  // read input.txt including N cases to solve
	{
		printf("Can't open the input.txt");
		exit(0);
	}
	if((out=fopen("output.txt","w"))==NULL)   // open output.txt to show the result
	{
		printf("Can't open the output.txt");
		exit(0);
	}
	
	fscanf(in,"%d",&N);                    //scanf the number of the case
	
	if(N==0){                              //when N=0,error
	   fprintf(out,"Empty data!!");
	   exit(0);
	   }
	   
	for(i=0;i<N;i++){
	    m=0;                                   //initialize m when every case begin
        flag=0;                                //initialize flag when every case begin
        for(j=0;j<4;j++){                   //scanf the data of the door
	       door[j]=(NOD)malloc(sizeof(struct nod));
           fscanf(in,"%f",&door[j]->x);
           fscanf(in,"%f",&door[j]->y);
           fscanf(in,"%f",&door[j]->z);
           door[j]->location=locate(door[j]);
       }
       fscanf(in,"%f",&Lx);            //scanf the data of the room
	   fscanf(in,"%f",&Ly);
       fscanf(in,"%f",&Lz);

       doorcenter(door);                //compute the center nod of the door which is used to compare

       fscanf(in,"%d",&n);          //scanf the number of outlet
       
       if(n==0)
        flag=3;                              //when n=0,error

       for(j=0;j<n;j++){             //scanf the data of every outlet and initialize the item
            outlet[j]=(NOD)malloc(sizeof(struct nod));
            fscanf(in,"%f",&outlet[j]->x);
            fscanf(in,"%f",&outlet[j]->y);
            fscanf(in,"%f",&outlet[j]->z);
            outlet[j]->location=locate(outlet[j]);
            outlet[j]->num=j;
            outlet[j]->next=NULL;
            if(outlet[j]->location==0)
                flag=2;             //the outlet is not in the wall
            if((outlet[j]->location==1||outlet[j]->location==3)&&(fabs(outlet[j]->z-doormid->z)<=H/2&&fabs(outlet[j]->x-doormid->x)<=B/2)&&(outlet[j]->location==doormid->location))   //the outlet and door in the same wall and the outlet is on the wall
                flag=2;              //the outlet is in on the door
            if((outlet[j]->location==2||outlet[j]->location==4)&&(fabs(outlet[j]->z-doormid->z)<=H/2&&fabs(outlet[j]->y-doormid->y)<=B/2)&&(outlet[j]->location==doormid->location))     //the outlet and door in the same wall and the outlet is on the wall
                flag=2;              //the outlet is in on the door
            if(outlet[j]->x<0||outlet[j]->x>Lx||outlet[j]->y<0||outlet[j]->y>Ly||outlet[j]->z<0||outlet[j]->z>Lz)
                flag=2;     //the outlet is not in the room
            
       }

       if((fabs(door[0]->x-doormid->x)!=fabs(door[1]->x-doormid->x))||(fabs(door[0]->y-doormid->y)!=fabs(door[1]->y-doormid->y))||(fabs(door[0]->z-doormid->z)!=fabs(door[1]->z-doormid->z)))
        flag=1;
	   if((fabs(door[2]->x-doormid->x)!=fabs(door[1]->x-doormid->x))||(fabs(door[2]->y-doormid->y)!=fabs(door[1]->y-doormid->y))||(fabs(door[2]->z-doormid->z)!=fabs(door[1]->z-doormid->z)))
        flag=1;         //the door is not a rectangle
       
       if(doormid->location==0)
        flag=1;         //the door is not in the wall
       for(j=0;j<4;j++){
        if(door[j]->x<0||door[j]->x>Lx||door[j]->y<0||door[j]->y>Ly||door[j]->z<0||door[j]->z>Lz)
            flag=1;
            }     //the door is not in the room

       if(flag==1)
        fprintf(out,"No.%d\t door is illegal!!\n",i+1);

       else if(flag==2)
        fprintf(out,"No.%d\t outlet is illegal!!\n",i+1);

       else if(flag==3)
        fprintf(out,"No.%d\t 0\n",i+1);

        else if(flag==0){
        for(j=0;j<n;j++)                //compute the disdant of every pair of outlet and store them
            for(k=j+1;k<n;k++){
                way[m]=(WAY)malloc(sizeof(struct edge));
		        way[m]->a=outlet[j];
                way[m]->b=outlet[k];
                way[m]->dis=findway(outlet[j],outlet[k]);
                m++;
            }

            result=kruskal(way,outlet,m,n);              //use kruskal algorithm to compute the minimum spanning tree
            fprintf(out,"No.%d\t %d\n",i+1,up(result));     //print the result to the out.txt
        }

    }
    return 0;
}



int locate(NOD a)
{
    int flag=0;
    if(a->y==0)
    flag=1;                    //when flag=1,the nod belongs to No.1 wall
    if(a->x==Lx)
    flag=2;                    //when flag=1,the nod belongs to No.2 wall
    if(a->y==Ly)
    flag=3;                    //when flag=1,the nod belongs to No.3 wall
    if(a->x==0)
    flag=4;                    //when flag=1,the nod belongs to No.4 wall
    return flag;               //from No.1 to No.4 is anticlockwise
}

float findway(NOD a,NOD b)
{
    NOD temp;
    float distant=0,d1,d2,d3;        //d1 is the way through the floor ,d2 is the way may cross the door through the beside wall,d3 is the way does not cross the door through the beside wall
    if(fabs(a->location-b->location)==2){              //the two outlets are in opposite wall
        if((doormid->location!=a->location)&&(doormid->location!=b->location)){   //the door is not in the same wall with both outlets
            d1=fabs(a->x-b->x)+fabs(a->y-b->y)+fabs(a->z+b->z);
            if(doormid->location==1){
                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);
            }
            if(doormid->location==2){
                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);
            }
            if(doormid->location==3){
                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);
            }
            if(doormid->location==4){
                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);
            }
            distant=min3(d1,d2,d3);
        }
        else{                                      //the door is in the same wall with one outlet
            if(b->location==doormid->location){           //assure the door is in the same wall with outlet a ,if not ,change them
                temp=(NOD)malloc(sizeof(struct nod));
                temp->x=a->x;
                temp->y=a->y;
                temp->z=a->z;
                temp->location=a->location;
                a->x=b->x;
                a->y=b->y;