用回溯法链表求解迷宫问题

<meta http-equiv="Content-Type" content="text/html; charset=gb2312">

用回溯法链表求解迷宫问题,并加上完整的人物演示过程 (按一键小人开始搜索）

创建人： 颜清国 2006年3月18日（下载源码(点击右键，目标另存为））
说明： 程序中按照上-右-下-左搜索，运行效果如图

#include"graphics.h"#include"stdio.h"#include"dos.h"#define LENGTH sizeof(struct Node)/******************************************* 定义全局变量，用来保存PEOPLE的位置      *******************************************/struct site{	int mapsite; /*定义是墙还是可移动的*/	int xnow;	int ynow;}psite[18][25];static int xp=1,yp=1,oldxp=1,oldyp=1;/*记录此时PAOPAO的位置和PAOPAO的个数*/typedef struct Node /*定义链表结点的结构体*/{ int x,y; int direction; struct Node*next;}node;/************************************栈的基本操作************************************/int findnext(node*head,node*p,int *direct);node*initstack(int x,int y,int direction);void push(node*head,node*p);void pop(node*head,node**p);void gettop(node*head,node*p);int stackempty(node*head);void dispstack(node*head);/****************************************** box(）函数用来画出PAOPAO总的活动范围   *******************************************/void box(int x1,int y1,int x2,int y2){	line(x1,y1,x1,y2);	line(x1,y1,x2,y1);	line(x2,y1,x2,y2);	line(x2,y2,x1,y2);}/******************************************* 函数用来在屏幕上画PEOPLE               *******************************************/void drawpeople(int x,int y,int color){	int people[8];	people[0]=x-6;	people[1]=y-4;	people[2]=x-10;	people[3]=y+10;	people[4]=x+10;	people[5]=y+10;	people[6]=x+6;	people[7]=y-4;	setcolor(color);	ellipse(x,y-7,0,360,10,4);	drawpoly(4,people);}/******************************************* 函数用来移动PEOPLE在屏幕上的位置       *******************************************/void movepeople(){  if(psite[yp][xp].mapsite==0 ) {  drawpeople(psite[yp][xp].xnow,psite[yp][xp].ynow,4);  drawpeople(psite[oldyp][oldxp].xnow,psite[oldyp][oldxp].ynow,1); }	}/******************************************* 函数用来初始化每个方格的属性和坐标，    ** 其中属性来自外部的文件                  *******************************************/void initsite(){	FILE*fp;	int i=0,j=0;	char ch;	if((fp=fopen("site.txt","r"))==NULL)	{		printf("the site not found");		exit(1);        }   while((ch=fgetc(fp))!=EOF)    { if(ch==10) continue;      else       {          psite[i][j].mapsite=ch-48;/*读取数组，存入MAPSITE[]*/          if((j+1)>=25)           i++;          j=(j+1)%25;       }    }		for(i=0;i<18;i=i++)/*初始化网格的中心坐标*/	{		for(j=0;j<25;j++)		{			psite[i][j].ynow=12+24*i;			psite[i][j].xnow=j*24+12;		}	}			for(i=0;i<18;i=i++)	{		for(j=0;j<25;j++)	  {		switch(psite[i][j].mapsite)		{		case 0:break;		case 1:			{				setfillstyle(8,4);				bar3d(psite[i][j].xnow-12,psite[i][j].ynow-12,psite[i][j].xnow+12,                                        psite[i][j].ynow+12,0,1);				floodfill(psite[i][j].xnow,psite[i][j].ynow,4);                                   /*画出地图对应的东西，0是走道，1是墙，2是栅栏*/				break;			}		case 2:			{				setfillstyle(11,3);				bar(psite[i][j].xnow-12,psite[i][j].ynow-12,psite[i][j].xnow+12,                                     psite[i][j].ynow+12);				floodfill(psite[i][j].xnow,psite[i][j].ynow,3);				break;			}		default:printf("error");exit(1);		}	  }       }}void initall(){	int driver,mode;	driver=DETECT;	mode=0;	registerbgidriver(EGAVGA_driver);	initgraph(&driver,&mode,"\\tc");	clearviewport();	setbkcolor(1);	box(0,0,600,432);	box(1,1,599,431);	initsite();	drawpeople(psite[yp][xp].xnow,psite[yp][xp].ynow,4);  /*paopao的初始显示位置*/}/***************************************创建头结点，并初始化第一个结点*X，Y，DIRECTION为NODE结构体的域值****************************************/node*initstack(int x,int y,int direction){ node*head=(node*)malloc(LENGTH);/*创建头结点*/ node*p=(node*)malloc(LENGTH); p->x=x;  /*初始化第一个结点*/ p->y=y; p->direction=direction; p->next=NULL; head->next=p; return head;}/*****************************************输出链表******************************************/void dispstack(node*head){  node*p=head->next;  if(stackempty(head))  {   printf("stack empty!");   return;  } 	 while(p->next!=NULL)         {           printf("(%d,%d) <----  ",p->x,p->y);           p=p->next;          }  printf("(%d,%d)",p->x,p->y);}/******************************************判断栈是否为空,返回1时为空，为0是非空*******************************************/int stackempty(node*head){ return(head->next==NULL);}/**********************************************栈顶的元素出栈*注意这里的第二叁数要为node**p*否则其返回时P指针变量的值不被改变**********************************************/void pop(node*head,node**p){ if(stackempty(head)) {  printf("stack empty!");  return; } else {  (*p)=head->next;  head->next=(*p)->next;  (*p)->next=NULL; }}/**********************************************一元素入栈**********************************************/void push(node*head,node*p){ node*q=(node*)malloc(LENGTH);  /*注意这里必须分配空间*/ if(stackempty(head)) {  printf("stack empty!");  return; } else {  q->x=p->x;  /*简单的拷贝P里面的值域*/  q->y=p->y;  q->direction=p->direction;  q->next=head->next;  head->next=q; }}/************************************************注意此处node*p指针变量的内容未变*但其指向的结构体单元的内容在返回后已经改变************************************************/void gettop(node*head,node*p){ p->x=head->next->x; p->y=head->next->y; p->direction=head->next->direction; /*注意此处不用p=head->next,防止指针域被复制而破坏链表*/}/**************************************************寻找下一个可以走的路径*找到返回1，否则返回0*其中direct是该可走点的方位**************************************************/int findnext(node*head,node*p,int *direct){ int d=head->next->direction,flag=0; int x=head->next->x,y=head->next->y; /*用来保存当前点的值，以便恢复*/     while((d < 5) && (flag==0))         {          d++;          p->x=x; /*每次换方位搜索还原该点值*/          p->y=y;           switch(d)           {            case 1:                     p->y --; /*搜索上*/                    break;            case 2:                    p->x ++; /*搜索右*/                    break;            case 3:                     p->y ++; /*搜索下*/                    break;            case 4:                     p->x --; /*搜索左*/                    break;           }           if(psite[p->y][p->x].mapsite==0)            {            flag=1;           }          }  if(d==5)    {   return 0; /*没有找到*/  }  else  {    (*direct)=d;   /*记录若下次退栈时从该方位+1处开始搜索*/    p->direction=0;/*新的结点从上方位开始搜索*/    return 1;  /*已找到下一路径*/  }}void delays(double second){  long far*ptr=(long far*)0x0040006c;  long current,final;  current=*ptr;  final=current+second*1193180/65536;  while(current<=final)  current=*ptr;}int main(){  int direct=0;  node*head,*p,*current=(node*)malloc(LENGTH);  current->next=NULL;  initall();  head=initstack(1,1,0);/*初始化头结点*/       while(!stackempty(head))       {         gettop(head,current);/*取前一个或后一个结点*/         if((current->x == 23) && (current->y == 16))/*已经找到出口*/         {          return 1;         }         else         {	    if(findnext(head,current,&direct))/*搜索下一个，并且找到*/            {              head->next->direction=direct;/*记录旧结点搜索到的方位*/              psite[head->next->y][head->next->x].mapsite=-1;/*标志已搜索过*/              push(head,current);/*当前结点入栈，其中方位号已置为上方*/            }            else /*当前结点为死结点，不可走，退栈*/            {             pop(head,¤t);/*回到了前一个结点*/             psite[head->next->y][head->next->x].mapsite=0;/*重新对上一结点搜索*/            }          }          oldxp=xp;          oldyp=yp;          xp=head->next->x;          yp=head->next->y;          movepeople();         delays(0.3);         }            }