迷宫问题求解
问题描述：
给定一个迷宫从入口到出口的路径，具体要求如下：
1.迷宫以16*16的矩阵存储在本地文件中，格式自定义。
2.迷宫障碍占一定的比列，
3.非递归形式求解问题
4.汇出迷宫路径（以命令行或者GUI）
5.无路可走时，请给出提示
本节是数据结构中运用栈思想去求解迷宫问题，本算法实现简单，代码仅供参考，如有疑问请评论联系：
#include <stdio.h> #include <stdlib.h> #define COUNT_I 17 #define COUNT_J 17 #define START_I 0 #define START_J 0 #define END_I 15 #define END_J 15 #define MAXSIZE 1000 //坐标位置结构体 typedef struct local{ int x; int y; }LOCAL; //栈结构 typedef struct stack{ LOCAL data[MAXSIZE]; int top; int base; }STACK; //初始化栈 STACK *InitStack(void) { STACK *maze; maze = (STACK *)malloc(sizeof(STACK)); maze->top = maze->base=-1; return maze; } //判栈空 int EmptyStack(STACK *maze) { if (maze->top ==maze->base) return 1; else return 0; } //判栈满 int IsFull(STACK *maze) { if (maze->top-maze->base== MAXSIZE) return 1; else return 0; } //入栈 int PushStack(STACK *maze, LOCAL *x) { if (maze->top <= MAXSIZE - 1){ maze->data[++maze->top] = *x; return 1; } else{ printf("栈已满\n"); return 0; } } //出栈 int PopStack(STACK *maze, LOCAL *x) { if (maze->top >maze->base){ *x = maze->data[maze->top]; maze->top--; return 1; } else{ printf("栈已空\n"); return 0; } } //走迷宫函数 int VistMaze(int maze[][COUNT_J], LOCAL path[][COUNT_J]) { int i, j; //初始化栈 STACK *stack; LOCAL temp; stack = InitStack(); temp.x = 0; temp.y = 0; if (maze[START_I][START_J] == 0) PushStack(stack, &temp); else return 0; while(!EmptyStack(stack)){ PopStack(stack, &temp); i = temp.x; j = temp.y; maze[i][j] = 2; if (i == END_I && j == END_J) break; //下 if (i + 1 <= END_I && maze[i + 1][j] == 0){ maze[i + 1][j] = 2; path[i + 1][j].x = i; path[i + 1][j].y = j; temp.x = i + 1; temp.y = j; PushStack(stack, &temp); } //右 if (j + 1 <= END_J && maze[i][j + 1] == 0){ maze[i][j + 1] = 2; path[i][j + 1].x = i; path[i][j + 1].y = j; temp.x = i; temp.y = j + 1; PushStack(stack, &temp); } //左 if (j - 1 >= 0 && maze[i][j - 1] == 0){ maze[i][j - 1] = 2; path[i][j - 1].x = i; path[i][j - 1].y = j; temp.x = i; temp.y = j - 1; PushStack(stack, &temp); } //上 if (i - 1 >= 0 && maze[i - 1][j] == 0){ maze[i - 1][j] = 2; path[i - 1][j].x = i; path[i - 1][j].y = j; temp.x = i - 1; temp.y = j; PushStack(stack, &temp); } } //如果到达终点而退出的循环则将路径标识出来 if (i == END_I && j == END_J){ maze[i][j] = 3; while(path[temp.x][temp.y].x != -1){ temp = path[temp.x][temp.y]; maze[temp.x][temp.y] = 3; } return 1; } else{ return 0; } } int main(void) { //迷宫 int i, j; FILE *fp; int maze[COUNT_I][COUNT_J] ; fp=fopen("keshedemo.txt","r"); if(!fp) printf("文件错误"); for(i=0;i<=16;i++) { for(j=0;j<=16;j++) { printf('da'); fscanf(fp,"%3d",&maze[i][j]); } } fclose(fp); fp=0; /* for (i=0;i<=16;i++) { for(j=0;j<=16;j++) fprintf(fp,"%3d",maze[i][j]); fprintf(fp,"\n"); } fclose(fp); */ //定义路径数组,将到(x,y)点的路径保存进数组 LOCAL path[COUNT_I][COUNT_J]; for(i = 0; i < COUNT_I; i++){ for(j = 0; j < COUNT_J; j++){ path[i][j].x = -1; path[i][j].y = -1; } } //打印出迷宫 printf("原迷宫：\n"); for(i = 0; i <= COUNT_I; i++) printf("-"); printf("\n"); for (i = 0; i < COUNT_I; i++){ printf("|"); for (j = 0; j < COUNT_J; j++){ if (maze[i][j] == 1) printf("*"); else printf(" "); } printf("|\n"); } for(i = 0; i <= COUNT_I; i++) printf("-"); printf("\n"); if (VistMaze(maze, path) == 0){ printf("没有路径可走\n"); exit(0); } //打印出迷宫和路径 printf("迷宫和路径：\n"); for(i = 0; i <= COUNT_I; i++) printf("-"); printf("\n"); for (i = 0; i < COUNT_I; i++){ printf("|"); for (j = 0; j < COUNT_J; j++){ if (maze[i][j] == 1) printf("*"); else if (maze[i][j] == 3) printf("0"); else printf(" "); } printf("|\n"); } for(i = 0; i <= COUNT_I; i++) printf("-"); printf("\n"); return 0; }
