迷宫-栈

注意di的运用，每个栈元素都记录了di值，通过while循环则不会重复找到上次已找过的路径。

总结：利用栈来解决迷宫的问题，是深度优先搜索。首先将入口入栈，然后寻找该入口下一步可走的方块（不仅要将方块入栈，还要记录该方块的方位，因此就像上面所说的一样，要注意di的运用，通过while循环，就不会重复找到上次已经招工的路径）。

 

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
#define M 8
#define N 8
struct
{
	int i;
	int j;
	int di;
}Stack[MaxSize];   //定义一个结构体数组

int top = -1;
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}
};
void mgpath()
{
	int i,j,di,find,k;
	top ++;
	Stack[top].i = 1; Stack[top].j = 1;Stack[top].di = -1;mg[1][1] = -1;
	while(top>-1)
	{
		i = Stack[top].i; j = Stack[top].j; di = Stack[top].di;
		if(i == M && j == N)
		{
			printf("迷宫路径如下：\n");
			for(k=0;k<=top;k++)
			{
				printf("\t(%d, %d)", Stack[k].i,Stack[k].j);
				if(k %5 == 0)
					printf("\n");
			}
			printf("\n");
			return ;
		}
		find = 0;
		while(di<3 && find ==0)
		{
			di++;
			switch(di)
			{
			case 0:i = Stack[top].i-1;j = Stack[top].j;break;
			case 1:i = Stack[top].i;j = Stack[top].j+1;break;
			case 2:i = Stack[top].i+1;j = Stack[top].j;break;
			case 3:i = Stack[top].i;j = Stack[top].j-1;break;
			}
			if(mg[i][j] == 0)
				find = 1;
		}
		if(find == 1)
		{
			Stack[top].di = di;
			top ++;
			Stack[top].i = i;
			Stack[top].j = j;
			Stack[top].di = -1;
			mg[i][j] = -1;
		}
		else
		{
			mg[Stack[top].i][Stack[top].j] = 0;
			top --;
		}
	}

}
int main(void)
{
	mgpath();
	return 0;
}