C语言 队列解决迷宫问题

对迷宫八个方向逐一搜索，若可通行这入队，并将已经通行的位置赋值1（避免重复搜索）

初始化队列

struct stack *Queue(){struct stack *S;S = (struct stack *)malloc(sizeof(struct stack));//分配队列空间 S->head=0;//队列首指针 S->tail=1;//队列尾指针 S->a[S->head] = (struct queue *)malloc(sizeof(struct queue));S->a[S->head]->high_seat=-1;//队列上一级位置 S->a[S->head]->i=1;S->a[S->head=0]->j=1;//迷宫入口 return S;} 

创建一个随机迷宫

int **Create_maze(int row,int line){int i,j;int **m;m = (int **)malloc(row * sizeof(int *));//分配迷宫空间 for(int i = 0; i < row; i++){m[i] = (int *)malloc(line * sizeof(int));//分配迷宫空间 }//printf("请输入迷宫图列(整个迷宫四周需均为墙体) 1 表示墙体，0 表示通路：\n");printf("随机生成一个%d行%d列的迷宫！\n",row,line);for(i=0;i=2){m[i][j]=0;}}m[1][1]=0;m[row-2][line-2]=0;}return m; }

迷宫路径搜索

//搜索迷宫路径
void Search_read(int **m,struct stack *S,int row,int line){int i,j;while(true){if(S->head==S->tail)  //若队列头指针和尾指针相遇则迷宫无解{printf("NOPATH 该迷宫无解！");exit(0);}i = S->a[S->head]->i;j = S->a[S->head]->j;if(i==row-2&&j==line-2) //若坐标到达出口则找到最后答案，结束搜索{break;}//	printf("%d\n",S->head);//	printf("%d\n",i);if(m[i-1][j]==0){Push(S,i-1,j,m);	}if(m[i-1][j+1]==0){Push(S,i-1,j+1,m);}if(m[i][j+1]==0){Push(S,i,j+1,m);}if(m[i+1][j+1]==0){Push(S,i+1,j+1,m);}if(m[i+1][j]==0){Push(S,i+1,j,m);}if(m[i+1][j-1]==0){Push(S,i+1,j-1,m);}if(m[i][j-1]==0){Push(S,i,j-1,m);}if(m[i-1][j-1]==0){Push(S,i-1,j-1,m);}S->head++;}} 

完整代码

#include 
#include #define SIZE 2500struct queue//队列结构体 {int i;int j;int high_seat;	};struct stack{struct queue *a[SIZE];int head;int tail;};//初始化队列 
struct stack *Queue(){struct stack *S;S = (struct stack *)malloc(sizeof(struct stack));//分配队列空间 S->head=0;//队列首指针 S->tail=1;//队列尾指针 S->a[S->head] = (struct queue *)malloc(sizeof(struct queue));S->a[S->head]->high_seat=-1;//队列上一级位置 S->a[S->head]->i=1;S->a[S->head=0]->j=1;//迷宫入口 return S;} //创建迷宫 
int **Create_maze(int row,int line){int i,j;int **m;m = (int **)malloc(row * sizeof(int *));//分配迷宫空间 for(int i = 0; i < row; i++){m[i] = (int *)malloc(line * sizeof(int));//分配迷宫空间 }//printf("请输入迷宫图列(整个迷宫四周需均为墙体) 1 表示墙体，0 表示通路：\n");printf("随机生成一个%d行%d列的迷宫！\n",row,line);for(i=0;i=2){m[i][j]=0;}}m[1][1]=0;m[row-2][line-2]=0;}return m; }//入队
void Push(struct stack* S,int i,int j,int **m){S->a[S->tail] = (struct queue *)malloc(sizeof(struct queue));S->a[S->tail]->i=i;//保存该通路行号 S->a[S->tail]->j=j;//保存该通路列号 S->a[S->tail]->high_seat=S->head; //保存该通路上一通路下标 S->tail++;m[i][j]=1;}//打印迷宫
void Printf_m(int **m,int row,int line){int i,j;printf("迷宫样式：\n");for(i=0;itail--;printf("迷宫最佳路径如下：\n"); do{	printf("(%d,%d ) ",S->a[S->tail]->i,S->a[S->tail]->j);S->tail=S->a[S->tail]->high_seat;}while((S->a[S->tail]->high_seat!=-1));	printf("(1,1)");} //搜索迷宫路径
void Search_read(int **m,struct stack *S,int row,int line){int i,j;while(true){if(S->head==S->tail){printf("NOPATH 该迷宫无解！");exit(0);}i = S->a[S->head]->i;j = S->a[S->head]->j;if(i==row-2&&j==line-2){break;}//	printf("%d\n",S->head);//	printf("%d\n",i);if(m[i-1][j]==0){Push(S,i-1,j,m);	}if(m[i-1][j+1]==0){Push(S,i-1,j+1,m);}if(m[i][j+1]==0){Push(S,i,j+1,m);}if(m[i+1][j+1]==0){Push(S,i+1,j+1,m);}if(m[i+1][j]==0){Push(S,i+1,j,m);}if(m[i+1][j-1]==0){Push(S,i+1,j-1,m);}if(m[i][j-1]==0){Push(S,i,j-1,m);}if(m[i-1][j-1]==0){Push(S,i-1,j-1,m);}S->head++;}} int main(){ int **m;int row,line;struct stack *S;S = Queue();printf("请输入迷宫行数：\n");scanf("%d",&row);printf("请输入迷宫列数：\n");scanf("%d",&line);m = Create_maze(row,line);Printf_m(m,row,line);//打印迷宫 Search_read(m,S,row,line);Printf_read(S);return 0;} 

运行结果

迷宫为8方向搜索，即可歇着走。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！