数据结构迷宫问题的实现

#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(); }