electric wiring.c

一个自己用C编的关于贪婪算法的例子

/****************************************************************
*   File Name: Electric Wiring.c                                *
*   Purpose: To compute the nearest integer length of wire      *
*            which can have all the outlets connected.          *
*   Author: Yan Bing                                            *
*   Created date: 2005-12-19	                                *
****************************************************************/

#define OUTLETNUM 20      /* The largest number of the outlets */
#include <stdio.h>
#include <stdlib.h>

struct point              /* Define the data structure of points */
{
	float x;
	float y;
	float z;
};

struct EdgeStruct         /* Define the segment of wire between two outlets */
{
	int sp;
	int ep;
	float len;
};
typedef struct EdgeStruct *Edge;

float length,width,height;/* Parameters of the room */

/****************************************************************
*				  About Length of Edges                         *
*   Compute the shortest distance between two outlets.          *
****************************************************************/

float top,bottom,left,right,front,back,ldoor,sdoor;/* Parameters of the door */

/* Check on which wall the outlet is */
int checkwall(struct point outlet)
{
	if(outlet.y==0.0)             /* On the first wall */
	   return 0;
	if(outlet.x==length)          /* On the second wall */
		return 1;
	if(outlet.y==width)           /* On the third wall */
        return 2;
	if(outlet.x==0.0)             /* On the fourth wall */
		return 3;
	printf("The posion of the outlet is wrong.\n");
	return -1;                    /* Not on the wall, and the outlet is not legal */
}				

/* compute the lenth of the shortest path from a outlet to the Z-axis deasil */
float lengthz(struct point tmp)
{
	switch(checkwall(tmp)){
		case 0:
            return(tmp.x);                    /* The outlet on the first wall */
		case 1:
            return(length+tmp.y);             /* The outlet on the second wall */
		case 2:
            return(2*length+width-tmp.x);     /* The outlet on the third wall */
		case 3:
            return(2*length+2*width-tmp.y);   /* The outlet on the fourth wall */
		default:
            return -1;                        /* The outlet not on any wall */
	}
}

/* Return the absoolute value of x */
float abso(float x)
{
	if(x>0)
		return x;
	else
		return -x;
}

/* Return the larger one of a and b */
float Max(float a,float b)
{
	if(a>b)
	   return a;
	else
	   return b;
}

/* Return the smaller one of a and b */
float Min(float a,float b)
{
    if(a>b)
        return b;
    else
        return a;
}

/* Compute the parameters of the door */
void PositionDoor(struct point door[])
{
    right=Max(Max(door[0].x,door[1].x),Max(door[2].x,door[3].x));
	left=Min(Min(door[0].x,door[1].x),Min(door[2].x,door[3].x));
    front=Max(Max(door[0].y,door[1].y),Max(door[2].y,door[3].y));
	back=Min(Min(door[0].y,door[1].y),Min(door[2].y,door[3].y));
    top=Max(Max(door[0].z,door[1].z),Max(door[2].z,door[3].z));
	bottom=Min(Min(door[0].z,door[1].z),Min(door[2].z,door[3].z));
	ldoor=Max(Max(lengthz(door[0]),lengthz(door[1])),Max(lengthz(door[2]),lengthz(door[3])));
	sdoor=Min(Min(lengthz(door[0]),lengthz(door[1])),Min(lengthz(door[2]),lengthz(door[3])));
}

/* Find the shortest length of edge between two outlets */
float shortlen(struct point outlet1, struct point outlet2)
{
    float lout,sout;
    float path1,path2,path3,dist;
    
    lout=Max(lengthz(outlet1),lengthz(outlet2));
	sout=Min(lengthz(outlet1),lengthz(outlet2));
    switch((int)abso(checkwall(outlet1)-checkwall(outlet2))){
        case 0:                                              /* The outlets are on the same wall */
        case 1:                                              /* The outlets are on two adjacent walls */
            if(outlet1.z<=bottom || outlet2.z<=bottom || outlet1.z>=top || outlet2.z>=top)
                return lout-sout+abso(outlet1.z-outlet2.z);
            else if(ldoor<lout && sdoor>sout){
                path1=lout-sout+abso(top-outlet1.z)+abso(top-outlet2.z);
                path2=lout-sout+abso(bottom-outlet1.z)+abso(bottom-outlet2.z);
                path3=2*(length+width)-(lout-sout)+abso(outlet1.z-outlet2.z);
                return Min(Min(path1,path2),path3);
            }else
                return lout-sout+abso(outlet1.z-outlet2.z);
        case 2:                                              /* The outlets are on two opposite walls */
            if((sout>sdoor && sout<ldoor) || (lout>sdoor && lout<ldoor)){
                path1=lout-sout+abso(outlet1.z-outlet2.z);
                path2=2*(length+width)-(lout-sout)+abso(outlet1.z-outlet2.z);
                path3=Min(path1,path2);
                if(outlet1.z>=top || outlet2.z>=top){      /* One of the outlets is on the door */
                    if(checkwall(outlet1)==0 || checkwall(outlet1)==2){
                        path1=outlet1.z+outlet2.z+width+abso(outlet1.x-left)+abso(outlet2.x-left);
                        path2=outlet1.z+outlet2.z+width+abso(outlet1.x-right)+abso(outlet2.x-right);
                    }else if(checkwall(outlet1)==1 || checkwall(outlet1)==3){
                        path1=outlet1.z+outlet2.z+width+abso(outlet1.y-front)+abso(outlet2.y-front);
                        path2=outlet1.z+outlet2.z+width+abso(outlet1.y-back)+abso(outlet2.y-back);
                    }
                }else                                      /* One of the outlets is under the door */
                    path1=path2=outlet1.z+outlet2.z+width+abso(outlet1.x-outlet2.x);
            }else{
                if(outlet1.z<=bottom || outlet2.z<=bottom || outlet1.z>=top || outlet2.z>=top){
                    path1=lout-sout+abso(outlet1.z-outlet2.z);
                    path2=2*(length+width)-(lout-sout)+abso(outlet1.z-outlet2.z);
                }else if(ldoor<lout && sdoor>sout){
                    path1=lout-sout+abso(top-outlet1.z)+abso(top-outlet2.z);
                    path2=lout-sout+abso(bottom-outlet1.z)+abso(bottom-outlet2.z);
                    path1=Min(path1,path2);
                    path2=2*(length+width)-(lout-sout)+abso(outlet1.z-outlet2.z);
                }else{
                    path1=2*(length+width)-(lout-sout)+abso(top-outlet1.z)+abso(top-outlet2.z);
                    path2=2*(length+width)-(lout-sout)+abso(bottom-outlet1.z)+abso(bottom-outlet2.z);
                    path1=Min(path1,path2);
                    path2=lout-sout+abso(outlet1.z-outlet2.z);
                }
                if(checkwall(outlet1)==0 || checkwall(outlet1)==2)
                    path3=outlet1.z+outlet2.z+width+abso(outlet1.x-outlet2.x);
                else if(checkwall(outlet1)==1 || checkwall(outlet1)==3)
                    path3=outlet1.z+outlet2.z+length+abso(outlet1.y-outlet2.y);
            }
            return Min(Min(path1,path2),path3);
        case 3:                                              /* The outlets are on two adjacent walls */
            if(outlet1.z<bottom || outlet2.z<bottom || outlet1.z>top || outlet2.z>top)
                return 2*(length+width)-(lout-sout)+abso(outlet1.z-outlet2.z);
            else if(ldoor<sout || sdoor>lout){
                path1=2*(length+width)-(lout-sout)+abso(top-outlet1.z)+abso(top-outlet2.z);
                path2=2*(length+width)-(lout-sout)+abso(bottom-outlet1.z)+abso(bottom-outlet2.z);
                path3=lout-sout+abso(outlet1.z-outlet2.z);
                return Min(Min(path1,path2),path3);
            }else
                return 2*(length+width)-(lout-sout)+abso(outlet1.z-outlet2.z);
    }
}

/****************************************************************
*				  About Heap                                    *
*   Build a heap with the edges between the outlets             *
****************************************************************/

struct HeapStruct         /* Define the data structure of the collection of the segments of wire */
{
	int Capacity;
	int Size;
	Edge Elements;
};
typedef struct HeapStruct *PriorityQueue;

/* Initialize the PriorityQueue composed of MaxElements of edges */
PriorityQueue InitializeHeap(int MaxElements)
{
    PriorityQueue H;
    H=(PriorityQueue)malloc(sizeof(struct HeapStruct));
    if(H==NULL){
        printf("Fail to malloc space for heap.\n");
        exit(0);
    }
    H->Elements=(Edge)malloc(sizeof(struct EdgeStruct)*(MaxElements+1));
    if(H->Elements==NULL){
        printf("Fail to malloc space for heap.\n");
        exit(0);
    }
    H->Capacity=MaxElements;
    H->Size=0;
    H->Elements[0].len=-1;
    return H;
}

/* Delete the minimun element in the PriorityQueue H */
Edge DeleteMin(PriorityQueue H)
{
    int i,Child;
    struct EdgeStruct MinElement;
   
    MinElement.len=H->Elements[1].len;             /* Save the min element */
    MinElement.sp=H->Elements[1].sp;
    MinElement.ep=H->Elements[1].ep;
    for(i=1;i*2<H->Size;i=Child){                  /* Find smaller child */
        Child=i*2;
        if(Child<H->Size-1 && H->Elements[Child+1].len<H->Elements[Child].len)
            Child++;
        if(H->Elements[H->Size].len>H->Elements[Child].len){/* Percolate one level */
			H->Elements[i].len=H->Elements[Child].len;
			H->Elements[i].sp=H->Elements[Child].sp;
			H->Elements[i].ep=H->Elements[Child].ep;
		}else
            break;                                  /* Find the proper position */
    }
    H->Elements[i].len=H->Elements[H->Size].len;
    H->Elements[i].sp=H->Elements[H->Size].sp;
    H->Elements[i].ep=H->Elements[H->Size].ep;
    H->Elements[H->Size].len=MinElement.len;        /* Save the min element at the last element*/
    H->Elements[H->Size].sp=MinElement.sp;
    H->Elements[H->Size].ep=MinElement.ep;
    return &H->Elements[H->Size--];
}

/* Percolate down the element on the positin p in the PriorityQueue H */
void PercolateDown(int p, PriorityQueue H)
{
	int child,Tmpsp,Tmpep;
	float Tmp;
	
    Tmp=H->Elements[p].len;
	Tmpsp=H->Elements[p].sp;
	Tmpep=H->Elements[p].ep;
    for(;p*2<=H->Size;p=child){           /* Find smaller child */
        child=p*2;
		if(child!=H->Size&&H->Elements[child].len>H->Elements[child+1].len)
            child++;
		if(H->Elements[child].len>Tmp)    /* Percolate one level */
		    break;          
		else{                             /* Find the proper position */
		    H->Elements[p].len=H->Elements[child].len;
		    H->Elements[p].sp=H->Elements[child].sp;
            H->Elements[p].ep=H->Elements[child].ep;
        }
	}
	H->Elements[p].len=Tmp;
	H->Elements[p].sp=Tmpsp;
	H->Elements[p].ep=Tmpep;
}

/* Build the heap in the Initialized PriorityQueue H */
void BuildHeap(PriorityQueue H, int num, struct point outlet[])
{
	int i,j;
    int edgnum=1;
	for(i=0;i<num;i++){
		for(j=0;j<i;j++){
			H->Elements[edgnum].sp=i;
			H->Elements[edgnum].ep=j;
			H->Elements[edgnum].len=shortlen(outlet[i],outlet[j]);/* Compute the length of the edge between i and j */
			edgnum++;
		}
	}
	H->Size=--edgnum;
	for(i=edgnum/2;i>0;i--)
	   PercolateDown(i,H);                                        /* Keep the heap order of the PriorityQueue H */
}

/* Free the priorityQueue H */
void FreeHeap(PriorityQueue H)
{
    if(H!= NULL)
    {
         free(H->Elements);
         free(H);
    }
}

/****************************************************************
*				  About Kruskal's Algorithm                     *
*   Find the minimum spanning tree, and compute its length      *
****************************************************************/

/* Initialize the elements in the set */
void InitializeSet(int set[],int num)
{
	int i;
	for(i=0;i<num;i++)
        set[i]=-1;
}	

/* Find the root of the tree in which the x1 is */
int find(int arr[],int x1)                                   
{
	while(arr[x1]>=0)
		x1=arr[x1];
	return x1;
}

/* Connect the points x1 and x2 */
void unit(int arr[],int x1,int x2)
{                          
	arr[find(arr,x2)]=find(arr,x1);
}

/* Find the minimum spanning tree, and return its length */
float kruskal(int num, struct point outlet[])
{
    int Edges=0;
	float res=0;
	int set[OUTLETNUM];
	PriorityQueue H;
	Edge temp;
	
	H=InitializeHeap(num*(num-1)/2);         /* Initialize the PriorityQueue */
	BuildHeap(H,num,outlet);                 /* Build the heap with the edge between every two outlets */
	InitializeSet(set,num);                  /* Initialize the set */
	while(Edges<num-1){
		temp=DeleteMin(H);                   /* Delete the edge in the PriorityQueue H with the smallest length */
		if(find(set,temp->sp)!=find(set,temp->ep)){
			unit(set,temp->sp ,temp->ep);    /* Accept the edge */
			res+=temp->len;
			Edges++;
		}
	}
	FreeHeap(H);                             /* Free the space of the priorityQueue H*/
	return res;
}

/****************************************************************
*				  About the Mian Function                       *
*   Read the input file, and record the answer in output file   *
****************************************************************/

int main(void)
{
	FILE *inputfp,*outputfp;
	
	struct point outlet[OUTLETNUM],door[4];
	int i,N;
	float result;
	
	if((inputfp=fopen("input.txt","r"))==NULL){                  /* Open the input file for reading */
        printf("Cannot open \"input.txt\" file\n");              /* Error happens when open the input file */
        exit(0);
    }
    if((outputfp=fopen("output.txt","w"))==NULL){                /* Create the output file for writing */
        printf("Cannot open \"output.txt\" file\n");             /* Error happens when open the input file */
        exit(0);
    }
	while(fscanf(inputfp,"%f%f%f",&door[0].x,&door[0].y,&door[0].z)!=EOF){
		for(i=1;i<4;i++)                                         /* Obtain the coordinates of the door */
			fscanf(inputfp,"%f%f%f",&door[i].x,&door[i].y,&door[i].z);
		fscanf(inputfp,"%f%f%f",&length,&width,&height);         /* Obtion the size of the room */
		PositionDoor(door);                                      /* Compute the parameters of the door */
		fscanf(inputfp,"%d",&N);                                 /* Obtion the number of the outlets */
		for(i=0;i<N;i++)                                         /* Obtion the coordinates of every outlet */
			fscanf(inputfp,"%f%f%f",&outlet[i].x,&outlet[i].y,&outlet[i].z);
		result=kruskal(N,outlet);                                /* Compute the length of wire */
		fprintf(outputfp,"%d\n",(result-(int)result>0)?((int)result+1):(int)result);
	}
	fclose(inputfp);
	fclose(outputfp);
	return 0;
}