迷宫-队列

#include <stdio.h>#include <stdlib.h>#define M 8#define N 8#define MaxSize 100int mg[M+2][N+2] = {{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}};struct{int i;int j;int pre;}Queue[MaxSize];int front = -1;int rear = -1;void printmg(int front){printf("k = %d\n", front);int k = front,j,ns = 0;while(k != 0){j = k;k = Queue[j].pre;Queue[j].pre = -1;}printf("迷宫路径如下：\n");k = 0;while(k<MaxSize){if(Queue[k].pre == -1){ns++;printf("\t(%d,%d) ",Queue[k].i,Queue[k].j);if(ns%5 == 0)printf("\n");}k++;}}void mgpath(){int i = 0,j = 0,find = 0, di = -1;rear++;Queue[rear].i = 1; Queue[rear].j = 1; Queue[rear].pre = -1;mg[i][j] = -1;while(front<=rear && !find){front++;i = Queue[front].i; j = Queue[front].j;if(i == M && j == N){find = 1;printmg(front);//return ;}for(di=0;di<4;di++){switch(di){case 0:i = Queue[front].i - 1;j = Queue[front].j;break;case 1:i = Queue[front].i;j = Queue[front].j + 1;break;case 2:i = Queue[front].i + 1;j = Queue[front].j;break;case 3:i = Queue[front].i;j = Queue[front].j - 1;break;}if(mg[i][j] == 0){rear++;Queue[rear].i = i;Queue[rear].j = j;Queue[rear].pre = front;mg[i][j] = -1;}}}if(!find)printf("找不到路径！\n");}int main(void){mgpath();return 0;}