学步园

迷宫问题的总体思路是，从迷宫的入口出发，沿着某一个方向向前试探，若能够行得通，则继续往前走，否则原来返回，再换另一个方向继续试探，直到所有可能的通路都被试探过，为了保证在任何一个位置都能够原来返回，需要设置一个堆栈结构来保存从入口到当前位置的路径。
迷宫可以用一个二维数组maze[1..m][1..n]来表示。数组中的元素值为1时表示该点道路阻塞，为0时表示该点可以进入，这里假定迷宫的入口处元素为maze[1][1], 出口处元素为maze[m][n],那么在maze[1][1]和maze[m][n]处元素值必为0，为了避免走回已经进入过的点，凡是进入过的点应该做一个标记，这里将其赋予一个非0非1的值，假定为2.

在任意时刻，在迷宫中的位置可以用所在点的行坐标和列坐标表示，这样在迷宫中的某一点位置(i, j)时，其可能运动的方向有8个方向，它的位置可从当前位置的坐标推算，如下：

但是按照这种规则，不是每个位置都有8个方向可以选择，比如在迷宫的4个角和边界上，为了避免讨论边界问题，可以在整个迷宫外面套上一圈其值均为1的元素，因此，作为表示迷宫的二维数组实际上是maze[0..m+1][0..n+1].

为了简化运算，将当前位置(i, j)及其相邻8个位置的坐标关系建立一个数组move[0..7][0..1], 假定每次试探的方向都是从正北方向开始，则数组可表示为：

move[ 8 ][ 2 ] = {
 { -1, 0 },
 { -1, 1 }, 
 { 0, 1 }, 
 { 1, 1 }, 
 { 1, 0 },
 { 1, -1 },
 { 0, -1 }, 
 { -1, -1 } }

具体算法描述如下函数int mazepath( int maze[][MaxN], int m, int n )：

#include<stdlib.h>
#include<stdio.h>

#define MaxN 100
#define MaxMN 10000

int mazepath( int maze[][MaxN], int m, int n ){     /* m, n是迷宫的维数 */
	int stack[ MaxMN ][ 3 ];            /* stack数组用于记录已走过的路径的点(i,j)及选择的方向 */
	int move[ 8 ][ 2 ] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } }; /* 移动下一步的方向 */
	int p, i, j, k, g, h, top = 0;    /* i,j用于记录当前位置的(i,j),(g,h)用于记录下一步的位置 */
	maze[ 1 ][ 1 ] = 2;               /* 起始位置maze[1][1]置一个非0非1的整数 */
	stack[ 0 ][ 0 ] = 1;              /* stack数组记录第一个位置的坐标 */
	stack[ 0 ][ 1 ] = 1;
	stack[ 0 ][ 2 ] = 1;

	while( top >= 0 ){               /* 如果当前位置没有下一步可走，则退栈返回上一个位置的下一个方向 */
		i = stack[ top ][ 0 ];
		j = stack[ top ][ 1 ];
		k = stack[ top-- ][ 2 ] + 1;   /* k为方向数，初始值为2，即方向向东，+1表示移向下一个方向 */
		while( k < 8 ){
			g = i + move[ k ][ 0 ];   /* 计算下一个位置的坐标(g,h) */
			h = j + move[ k ][ 1 ];
			if( g == m && h == n && maze[ g ][ h ] == 0 ){    /* 若找到了迷宫的出口 */
				printf( "\n找到一条通道！\n" );
				for( p = 0; p <= top; p++ )  /* 遍历堆栈，打印堆栈信息 */
					printf( "(%d, %d)\n", stack[ p ][ 0 ], stack[ p ][ 1 ] );
				printf( "(%d, %d)\n", i, j );      /* 打印当前位置(i,j)和出口位置(m,n) */
				printf( "(%d, %d)\n", m, n );
				return 1;
			}
			if( maze[ g ][ h ] == 0 ){    /* 找到通路上的一个位置(g,h) */
				maze[ g ][ h ] = 2;       /* 在maze[g][h]置一个非0非1的整数 */
				stack[ ++top ][ 0 ] = i;  /* 将当前位置信息(i,j)及所选方向数入栈 */
				stack[ top ][ 1 ] = j;
				stack[ top ][ 2 ] = k;

				i = g;    /* 更新当前位置信息为通路上的下一个位置 */
				j = h;
				k = 0;
			}
			k++;
		}
	}
	printf( "\n迷宫中没有发现通路!\n" );
	return 0;
}

int main(){
	int maze[8][MaxN] = {
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
		{ 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1 },
		{ 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1 },
		{ 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1 },
		{ 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1 },
		{ 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1 },
		{ 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1 },
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
	};
	mazepath( maze, 6, 9 );
}