运行就进入死循环，迷宫的地图没设置好， 深度搜索： /*迷宫的算法*/ /* 先建立迷宫（外围建筑围墙），设置入口和出口。建立链表，把第一个点（入口）入舰，同时做好 标记，以免重复入舰。a：判断舰顶元素的东面是否可通，若可通则将其入舰 ，同时做好标记， 以免重复入舰；若不通则判断舰顶元素的南面是否可通，依此操作至北面元素。 判断新的舰顶元素是否为出口 ，若是，则报告结束，并打印出路径；否则递归操作a：。 若舰顶元素其余三面皆不通 ，则将舰顶元素其重新设定为不通，以免以后再走弯路。然后退舰。 重复a；操作。 若退回到入口，则表示迷宫走不通，报告不通。*/ #include<stdio.h> #include<stdlib.h> #include<string.h>
#define OK 1 #define NO 0 #define OVERFLOW 1 #define M 5 #define N 5
typedef struct poi{/*建立链表结构，存储每个路径点的有关数据；横坐标，纵坐标，所指方向和向下的指针*/ int x; int y; char *p; struct poi *next; } Point; Point *head; char a[100][200]; char FX[14]={'E','S','W','N','E','S','W', 'E','N','W','S','E','N','W',};/*存储方向*/ int MG_S[M+2][N+2], MG[M+2][N+2], In[2], Out[2], X_Y[2];/*分别存储迷宫，入，出口和当前坐标*/ int FX_Head, FX_Tail, row=0;
void Build(void);/*建立迷宫（外围建筑围墙），设置入口和出口*/ void B_IO(void); void Copy(void); void B_Head(int start); void Go(void);/*主要操作，可递归调用*/ int Judge(void);/*判断下一结点是否可通，若可通则记录该点坐标，并返回可通标志*/ void Print(Point *head);/*打印行进路径*/ void Push(Point **head);/*将当前结点入舰，并做记号表示该点已经走过*/ void Pop(Point **head);/*将当前结点退舰，并做记号表示该点不通*/ void Pop_Or_No(int end);/*判断舰顶元素所指方向是否为北，若是则退舰，否则继续判断下一方向*/ void Store(Point *head); void Pai_Xu(void); void Xiao_Chu(void); void Print_Total(void); void Free(void); void Change(Point **head);/*原链表从表头入出舰，故表头元素表示出口坐标，表尾元素表示入口坐标， 打印出来的路径图是反的，不合习惯，故用此函数将表头和表尾互换，其他 元素依次调换*/
int main(void) { int flag, i, m, n; a: Build(); b: for(i=0; i<4; i++) { FX_Head = i; FX_Tail = i + 3; if(i == 0) B_IO(); Copy(); B_Head(FX_Head); Go(); } for(i=7; i<11; i++) { FX_Head = i; FX_Tail = i + 3; Copy(); B_Head(FX_Head); Go(); } Pai_Xu(); Xiao_Chu(); Print_Total(); puts("do you want play again? 2 to change the I_O,1 to change the MG, 0 to quit: "); scanf("%d", &flag); if(flag == 1) { Free(); row = 0; goto a; } else if(flag == 2) { Free(); row = 0; goto b; } system("pause"); return 0; }
void Build(void) /*建立迷宫（外围建筑围墙），设置入口和出口*/ { int i, j; puts("Build the MG"); for(i=1; i<=M; i++) for(j=1; j<=N ; j++) scanf("%d", &MG_S[i][j]); fflush(stdin); for(i=0; i<=M+1; i++) /*外围建筑围墙*/ { MG_S[i][0] = 1; MG_S[i][N+1] = 1; } for(j=0; j<=N+1; j++) /*外围建筑围墙*/ { MG_S[0][j] = 1; MG_S[M+1][j] = 1; } }
void B_IO(void) { int i, j; for(i=0; i<=M+1; i++)/*输出迷宫图案*/ { for(j=0; j<=N+1; j++) printf("%d ", MG_S[i][j]); printf("\n"); } puts("Input the In Position"); for(i=0; i<2; i++) scanf("%d", &In[i]); puts("Input the Out Position"); for(i=0; i<2; i++) scanf("%d", &Out[i]); }
void Copy(void) { int i, j; for(i=0; i<=M+1; i++) /*把原始迷宫复制到待测迷宫中*/ for(j=0; j<=N+1; j++) MG[i][j] = MG_S[i][j]; }
void B_Head(int start) { head = (Point *)malloc(sizeof(Point));/*建立链表，把第一个点（入口）入舰*/ if(!head) { puts("出错了！"); getchar(); exit(OVERFLOW); } head->x = In[0]; head->y = In[1]; head->p = &FX[start]; head->next = NULL; MG[head->x][head->y] = -1;/*表示该点已经走过*/ }
void Go(void) /*主要操作，可递归调用*/ { int flag, i; flag = Judge(); /*判断下一结点是否可通*/ if(flag == 3) /*判断新的舰顶元素是否为出口 ，若是，则报告结束，并打印出路径*/ { Push(&head); puts("\nsuccess！"); Change(&head); Store(head); } else if(flag == 1)/*若可通则将其入舰 */ { Push(&head); Go(); } else /*若不通，则判断舰顶元素所指方向是否为北，以便决定是否退舰*/ Pop_Or_No(FX_Tail); }
int Judge(void) /*判断下一结点是否可通，若可通则记录该点坐标，并返回可通标志*/ { switch( *(head->p)) { case 'E': /*若舰顶元素指向东，则下一结点坐标为MG[head->x][head->y + 1]*/ { if(head->x == Out[0] && head->y + 1 == Out[1]) { X_Y[0] = head->x; X_Y[1] = head->y + 1; return 3; /*若下一结点可通，返回值1*/ } else if(MG[head->x][head->y + 1] == 0) { X_Y[0] = head->x; X_Y[1] = head->y + 1; return 1; /*若下一结点可通，返回值1*/ } else return 0; /*若下一结点不可通，返回值0*/ } case 'S': { if(head->x + 1 == Out[0] && head->y == Out[1]) { X_Y[0] = head->x + 1; X_Y[1] = head->y; return 3; /*若下一结点可通，返回值1*/ } else if(MG[head->x + 1][head->y] == 0) { X_Y[0] = head->x + 1; X_Y[1] = head->y ; return 1; } else return 0; } case 'W': { if(head->x == Out[0] && head->y - 1 == Out[1]) { X_Y[0] = head->x; X_Y[1] = head->y - 1; return 3; /*若下一结点可通，返回值1*/ } else if(MG[head->x][head->y - 1] == 0) { X_Y[0] = head->x; X_Y[1] = head->y - 1; return 1; } else return 0; } case 'N': { if(head->x - 1 == Out[0] && head->y == Out[1]) { X_Y[0] = head->x - 1; X_Y[1] = head->y; return 3; /*若下一结点可通，返回值1*/ } else if(MG[head->x-1][head->y] == 0) { X_Y[0] = head->x - 1; X_Y[1] = head->y; return 1; } else return 0; } } }
void Push(Point **head) /*将当前结点入舰，并做记号表示该点已经走过*/ { Point *r, *s;
s = (Point *)malloc(sizeof(Point)); if(!s) { puts("出错了！"); getchar(); exit(OVERFLOW); } s->x = X_Y[0]; s->y = X_Y[1]; s->p = &FX[FX_Head]; MG[s->x][s->y] = -1;/*表示该点已经走过*/ s->next = *head;; *head = s; }
void Pop_Or_No(int end) /*判断舰顶元素所指方向是否为北，若是则退舰，否则继续判断下一方向*/ { if(*(head->p) != FX[end]) { (head->p)++; Go(); } else { if(head->x == In[0] && head->y == In[1]) /*若退回到入口，且入口指向北，则表示迷宫走不通*/ puts("fail！"); else { Pop(&head); if(head->x == In[0] && head->y == In[1]) /*若退回到入口，且入口指向北，则表示迷宫走不通*/ { if(*(head->p) != FX[end]) { (head->p)++; Go(); } else puts("fail！"); } else Pop_Or_No(end); } } }
void Pop(Point **head) /*将当前结点退舰，并做记号表示该点不通*/ { Point *s; s = *head; *head = s->next; MG[s->x][s->y] = 1; /*记号表示该点不通*/ free(s); }
void Change(Point **head) //原链表从表头入出舰，故表头元素表示出口坐标，表尾元素表示入口坐标， { Point *p, *q, *r; //打印出来的路径图是反的，不合习惯，故用此函数将表头和表尾互换， //其他元素依次调换。 p = *head; q = p->next; while(q != NULL) { r = q->next; q->next = p; p = q; q = r; } (*head)->next = NULL; *head = p; }
void Print(Point *head) /*打印行进路径*/ { Point *r; r = head; while(r->next != NULL) { printf("(%d,%d)-> ", r->x, r->y); r = r->next; } printf("(%d,%d)", r->x, r->y); }
void Store(Point *head) { int i=0, flag=1; char *s; while(flag) { if(head->next != NULL) { a[row][i++] = '('; a[row][i++] = (char)(head->x + 48); a[row][i++] = ','; a[row][i++] = (char)(head->y + 48); a[row][i++] = ')'; a[row][i++] = '-'; a[row][i++] = '>'; a[row][i++] = ' '; head = head->next; } else flag = 0; } a[row][i++] = '('; a[row][i++] = (char)(head->x + 48); a[row][i++] = ','; a[row][i++] = (char)(head->y + 48); a[row][i++] = ')'; a[row][i++] = '\0'; row++; }
void Pai_Xu() { int i, j, min; char p[200]; for(i=0; i<row-1; i++) { min = i; for(j=i+1; j<row; j++) if(strlen(a[min]) > strlen(a[j]) ) min = j; if(min != i) { strcpy(p, a[i]); strcpy(a[i], a[min]); strcpy(a[min], p); } } }
void Xiao_Chu() { int i, j; char p[200]="fail"; for(i=0; i<row-1; i++) for(j=i+1; j<row; j++) if(strcmp(a[i], a[j]) == 0) strcpy(a[j], p); }
void Print_Total() { int i; puts("\nthe total root:"); for(i=0; i<row-1; i++) if(strcmp(a[i], "fail") != 0) puts(a[i]); }
void Free(void) { Point *r; while(head) { r = head; head = head->next; free(r); } }
