cymigong.cpp

一个迷宫问题的算法

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

#define maxsize 100
#define NULL 0

typedef struct
{
  int array[maxsize][maxsize];
  int max_x,max_y;
}sd;
 
typedef struct point
{
 int vex_x,vex_y;
 struct point *next;
 int direction;
}Point;

sd creat()
{
 int i,j,x;
 sd a;
 printf("enter row and lie:");
 scanf("%d%d", &a.max_x, &a.max_y);
 for(i=1;i<=a.max_x;i++)
 {
   printf("enter %d row:", i);
   for(j=1;j<=a.max_y;j++)
	   scanf("%d", &a.array[i][j]);  /*输入迷宫信息, 0为通路, 1为不通 */
 }
 return a;
}

  int found(int x, int y, Point *head)
  {
    Point *p=head;
	while(p!=NULL)
	{
	  if(x==p->vex_x && y==p->vex_y)
		  return 1;
	  p=p->next;
	}
	return 0;
  }

  Point *secret(sd a)
  {
   Point *top,*p;
   int i,j,m,x,y;
   p=(Point*)malloc(sizeof(Point));
   p->vex_x=1;p->vex_y=1;p->next=NULL;
   top=p;
   j=1;    /*j为方向,1,2,3,4分别为东,南,西,北 */
   do
   {
    while(j<=4)
	{
	  m=0;
	  x=top->vex_x;
	  y=top->vex_y;
	  switch(j)
	  {
	  case 1:if(y+1<=a.max_y && !a.array[x][y+1] && !found(x,y+1,top))  /*当前结点为0,没有在栈中出现,加入栈*/
			 {	
				 p=(Point*)malloc(sizeof(Point));
		         p->vex_x=x;p->vex_y=y+1;p->next=top;
				 top->direction=j;
		         top=p;m=1;
			 }
	  break;

	  case 2:if(x+1<=a.max_x && !a.array[x+1][y] && !found(x+1,y,top))
			 {		
				 p=(Point*)malloc(sizeof(Point));
		         p->vex_x=x+1;p->vex_y=y;p->next=top;
				 top->direction=j;
		         top=p;m=1;
			 }
	  break;
	  
	  case 3:if(y-1>=1 && !a.array[x][y-1] && !found(x,y-1,top))
			 {		
				 p=(Point*)malloc(sizeof(Point));
		         p->vex_x=x;p->vex_y=y-1;p->next=top;
				 top->direction=j;
		         top=p;m=1;
			 }
	  break;

	  case 4:if(x-1>=1 && !a.array[x-1][y] && !found(x-1,y,top))
			 {		
				 p=(Point*)malloc(sizeof(Point));
		         p->vex_x=x-1;p->vex_y=y;p->next=top;
				 top->direction=j;
		         top=p;m=1;
			 }
	  break;
	
	}
     if(m!=0)
	 {j=1;break;}
	 else j++;
   }
	
	if(j>4)
	{
	 if(top!=NULL)
	 {
	   top=top->next; j=top->direction+1; top->direction=j;
	 }
	 else return NULL;
	}
  }while(top->vex_x!=a.max_x || top->vex_y!=a.max_y);

   if(top->vex_x==a.max_x && top->vex_y==a.max_y ) top->direction=0;

   return top;
  }

     void  disp(Point *po)
	 {
	  int i=0, top=0;
	  Point *stack[maxsize];
	  if(po==NULL) printf("NO LOAD!\n");
	  else
	  {
	    while(po!=NULL)
		{
		  stack[top++]=po;
		  po=po->next;
		}
		while(top>0)
		{
		 top--;
		 printf("(%d,%d,%d)", stack[top]->vex_x, stack[top]->vex_y, stack[top]->direction);
		 i++;
		 if(i%8==0) printf("\n");
		}
	  }
	  printf("\n");
	 }
	 main()
	 {
	  sd road;
	  Point *po;
	  road=creat();
	  po=secret(road);
	  disp(po);
	  getch();
	 }