迷宫的算法 -- 业余空间-- 编程爱好者博客

深度搜索： /*迷宫的算法*/ /* 先建立迷宫（外围建筑围墙），设置入口和出口。建立链表，把第一个点（入口）入舰，同时做好标记，以免重复入舰。a：判断舰顶元素的东面是否可通，若可通则将其入舰，同时做好标记，以免重复入舰；若不通则判断舰顶元素的南面是否可通，依此操作至北面元素。判断新的舰顶元素是否为出口，若是，则报告结束，并打印出路径；否则递归操作a：。若舰顶元素其余三面皆不通，则将舰顶元素其重新设定为不通，以免以后再走弯路。然后退舰。重复a；操作。若退回到入口，则表示迷宫走不通，报告不通。*/ /*2005-4-22 梁见斌*/ #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); } } 广度搜索； /*可以玩多次*/ /*迷宫的算法*/ /* 先建立迷宫（外围建筑围墙），设置入口和出口。建立链表队列，把第一个点（入口）入队，同时做好标记，以免重复入队。依次判断队头元素的东，南，西，北面是否为出口，若是则打印路径，并发出成功信号；否则判断队头元素的该方向是否可通，若可通则将其入队，同时做好标记，以免重复入队；若未收到成功信号，则表示迷宫走不通，报告不通。*/ /*2005-4-22 梁见斌*/ #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, y; struct poi *pre, *next; } Point; Point *head, *front, *rear; int Z_X[7]={0, 1, 0, -1, 0, 1, 0}, Z_Y[7]={1, 0, -1, 0, 1, 0, -1};/*存储方向*/ int MG_S[M+2][N+2], MG[M+2][N+2], In[2], Out[2], row=0;/*分别存储迷宫，入，出口和当前坐标*/ char a[100][200]; void Build(void);/*建立迷宫（外围建筑围墙），设置入口和出口*/ void B_IO(void); void Copy(void); void Go(int m, int n) ;/*主要操作*/ void Print(Point *head);/*打印行进路径*/ Point *Change(void); void Free(void); void Store(Point *head); void Pai_Xu(void); void Xiao_Chu(void); void Print_Total(void); int main(void) { int flag, k; Build(); /*建立迷宫（外围建筑围墙），设置入口和出口*/ a: B_IO(); k = 1; b: Copy(); front = (Point *)malloc(sizeof(Point));/*建立链表，把第一个点（入口）入队*/ if(!front) { puts("出错了！"); getchar(); exit(OVERFLOW); } front->x = In[0]; front->y = In[1]; front->pre = NULL; front->next = NULL; MG[front->x][front->y] = -1;/*表示该点已经走过*/ rear = front; head = front; if(k == 1) { k++; Go(0,3); /*主要操作*/ Free(); goto b; } else if(k == 2) { k++; Go(1,4); /*主要操作*/ Free(); goto b; } else if(k == 3) { k++; Go(2,5); /*主要操作*/ Free(); goto b; } else Go(3,6); /*主要操作*/ Pai_Xu(); Xiao_Chu(); Print_Total(); puts("do you want play again? 1 to again, 0 to quit: "); scanf("%d", &flag); if(flag) { Free(); row = 0; goto a; } 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 Go(int m, int n) /*主要操作，可递归调用*/ { Point *s, *p, *q; int flag=0, fx, i, j; while(front) { for(fx=m; fx<=n; fx++) { i = front->x + Z_X[fx];/*下一结点的坐标*/ j = front->y + Z_Y[fx]; if( i == Out[0] && j == Out[1])/*判断队头元素的该方向是否为出口 */ { s = (Point *)malloc(sizeof(Point)); if(!s) { puts("出错了！"); getchar(); exit(OVERFLOW); } s->x = i; s->y = j; s->pre = front; s->next = NULL; q = rear; rear->next = s; rear = rear->next; MG[s->x][s->y] = -1;/*表示该点已经走过*/ flag = 1; /*发出成功信号*/ p = Change(); Store(p); rear = q; } else if(MG[i][j] == 0)/*判断队头元素的该方向是否可通，若可通则将其入队 */ { s = (Point *)malloc(sizeof(Point)); if(!s) { puts("出错了！"); getchar(); exit(OVERFLOW); } s->x = i; s->y = j; s->pre = front; s->next = NULL; rear->next = s; rear = rear->next; MG[s->x][s->y] = -1;/*表示该点已经走过*/ } } front = front->next; /*对头向下走，直到结尾*/ } if(flag == 0) /*若未收到成功信号，则表示迷宫走不通，报告不通。*/ puts("fail！"); } void Print(Point *head) /*打印行进路径*/ { Point *r; r = head; while(r->pre != NULL) { printf("(%d,%d)-> ", r->x, r->y); r = r->pre; } printf("(%d,%d)\n", r->x, r->y); } Point *Change(void) //原队列中队尾元素表示出口坐标，打印出来的路径图是反的， { Point *p, *r, *s; //故将原路径复制到新队列中，对调指针方向，以便打印顺序路径图， p = rear; s = (Point *)malloc(sizeof(Point)); if(!s) { puts("出错了！"); getchar(); exit(OVERFLOW); } s->x = p->x; s->y = p->y; s->pre = NULL; s->next = NULL; r = s; p = p->pre; while(p) { s = (Point *)malloc(sizeof(Point)); if(!s) { puts("出错了！"); getchar(); exit(OVERFLOW); } s->x = p->x; s->y = p->y; s->pre = r; s->next = NULL; r->next = s; r = s; p = p->pre; } return r; /*返回复制的新队列，以便打印*/ } void Free(void) { Point *r; while(head) { r = head; head = head->next; free(r); } } void Store(Point *head) { int i=0, flag=1; while(flag) { if(head->pre != 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->pre; } 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]); }

博客介绍

正文

迷宫的算法2005-04-24 22:17:00

评论