randmigong.c

一个寻找迷宫出口的算法,具有随机性选择,但绝无重复路程!

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct position
{
 int pointnum;
 int A_derect;
 int B_derect;
 int C_derect;
}point;

struct List
{
  int num;
  struct List *next,*font;
}*head_ptr,*head_front,*init(),*fly;

point *p;
point *q;
int tempsave;
point cross[25]={
	{0,1,0,0},
	{1,2,0,0},
    {2,0,0,3},
	{3,5,4,0},
	{4,0,0,0},
	{5,0,6,0},
    {6,0,7,24},
    {7,8,0,9},
    {8,0,0,0},
    {9,0,0,10},
    {10,0,11,0},
	{11,0,0,12},
	{12,0,0,13},
	{13,0,14,0},
	{14,0,0,15},
	{15,0,16,17},
	{16,0,0,0},
	{17,0,18,23},
	{18,0,19,0},
	{19,21,20,0},
	{20,0,0,0},
	{21,0,0,22},
	{22,0,0,0},
	{23,0,0,0},
	{24,0,0,0} 
	

};

struct List *init()
{
	struct List *newer,*head;
	newer=(struct List *)malloc(sizeof(struct List));
	newer->num=0;
	newer->next=NULL;
	newer->font=NULL;
	head=newer;
	return(head);
}

void addList(int x)
{
 	struct List *flow,*newer;
	flow=head_ptr;
	while(flow->next!=NULL)
		flow=flow->next;

   	newer=(struct List *)malloc(sizeof(struct List));
	newer->num=x;
	head_front=newer;
	newer->font=flow;
	flow->next=newer;
	newer->next=NULL;
}



void swap(point *pp)
{
 int turn;   
 int i;
 turn=rand()%6; 
 for(i=0;i<turn;i++)
  {
    tempsave=pp->A_derect;
    pp->A_derect=pp->B_derect;
    pp->B_derect=pp->C_derect;
	pp->C_derect=tempsave;

 } 
   
}

  void moveto(point cur,point pre,int flag)/*cur现在所在的位置，pre上次去的位置*/
{
 p=&cur;
 q=&pre; 
 swap(p);
 if(flag == 1)
 addList(p->pointnum);
 if(p->pointnum == 4)
   {
     printf("--->end");
     return ;
   }
   else if(p->A_derect != 0)
     {
          printf("--->%d",p->A_derect);
         
	  moveto(cross[p->A_derect],cross[p->pointnum],1); }

          else if(p->B_derect != 0)
	 	   {
                     printf("--->%d",p->B_derect);
                     moveto(cross[p->B_derect],cross[p->pointnum],1);
		   }
               else  if(p->C_derect != 0)
				 {
                                   printf("--->%d",p->C_derect);
                                    moveto(cross[p->C_derect],cross[p->pointnum],1);
				 }
                 else             
				 {  
                        
						  fly=head_front->font;	
						  head_front=head_front->font;             
				    	 printf("--->%d",fly->num);
                    if( cross[fly->num].A_derect== p->pointnum)
                              cross[fly->num].A_derect = 0;
                        else if(cross[fly->num].B_derect == p->pointnum)     
                                   cross[fly->num].B_derect = 0;
                             else if(cross[fly->num].C_derect == p->pointnum)    
                                         cross[fly->num].C_derect = 0;
							          
							         head_front->next=NULL; 							                
                                        
                                     moveto(cross[fly->num],cross[p->pointnum],0);									            



				 }
}



main()
{

 point start={0,1,0,0};
 head_ptr = init(); 
 srand((unsigned)time(NULL));
 printf("start-->\n"); 
 /*scanf("pointnum  %d, A_derect %d, B_derect  %d, C_derect %d\n",&(cross[i].pointnum),&(cross[i].A_derect),&(cross[i].B_derect),&(cross[i].C_derect));*/
  
  moveto(cross[0],start,1);
  getch();
 
}