迷宫-队列

求解迷宫路径时，使用的是循环队列，所以出队只是修改了方块在队列里的下标，并没有真正意义上的出队。

思路是：

1）先将入口（1,1）入队，在队列不为空时循环进行出队，称出队方块为当前方块；

2）如果当前方块是出口（8,8），则输出路径；

3）如果当前方块不是出口，则将当前方块邻近可走的方块全部入队，入队时要保存方块的mg[i][j]值为-1，以免重复走，并保存方块的pre值，即当前队列的front，表明上一方块在队列的中下标值，这样方便倒推路径时可通过当前方块找到上一方块。

4）输出时，通过输出当前方块，然后根据当前方块的pre值输出上一方块。

#include <stdio.h>
#include <stdlib.h>
#define M 8
#define N 8
#define MaxSize 100

int 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;
}