[程序实现] 010001100011111 (1)设计思想 100011011100111 当迷宫采用二维数组表示时,老鼠011000011110011 在迷宫中任一时刻的位置可由数组的110111011011 行列序号i,来表示。而从[[j位110100101111 置出发,可能的行进方向见下图1 001101110100101 如果[i][j周围位置均为0值,则老00110110100101 鼠可以选择这8个维之中的任一个作 011110011111111 为它的下一个位置。将这八个方向分00110110111101 别记作:E(东)、SE(东南、S(南)、110001101100000 SW(西南)、W(西)、N(西北)N00111110001110 (北)和NE(东北)。但是并非每-01001111101110 个位置都有8个相邻位置。如果[i][j 位于边界上,即i=1,或im,或jn,则相邻位置可能是5个或3个。为了避 免检查边界条件,将数组四周围用值为1的边框包围起来,这样二维数组 maze应该声明为maze[m+2][n+2]。 在迷宫中行进时,可能有多个行进方向可供选择,我们可以规定方向搜 索的次序是从东(E)沿顺时针方向进行。为了简化问题,规定[i][j的下 步位置坐标是[x][y],并将这8个方向上的x和y坐标的增量预先放在 个结构数组move[8]中(见图2)。该数组的每个分量有两个域dx和dy。例 如要向东走,只要在j值上加dy,就可以得到下一步位置的[x][y]的值为 [i][j+dy]。于是搜索方向的变化只是要令方向值dir从0增加到7,便可 以从move数组中得到从[i[j点出发搜索到的每一个相邻点[x][y] x=i+move [dir]. dx y=j+move [dir] dy 为了防止重走原路,我们规定对已经走到过的位置,将原值0改为-1 这既可以区别该位置是否已经走到过,又可以与边界值1相区别。当整个搜 索过程结束后,可以将所有的-1该回到0,从而恢复迷宫的原样。 这个计算机走迷宫的算法是:采取一步一步试探的方法。每一步都从东 (E)开始,按顺时针方向对8个方向进行探测,如某个方向上的 maze[x][y]=0,表示可以通行,则走一步;如 maze [x][y]=1,表示此方向上 不可通行,须换方向再试,直至8个方向都试过,maze[x][y]均为1,说明 此步已无路可走,须退回一步,再上一步的下一个方向上重新探测。为此须 设置一个栈,用来记录所走过的位置和方向(i,j,dir)。当退回一步时,就 从栈中退回一个元素,以便在上一个位置的下一个方向上探测,如果有找到 个进行方向,这把但前位置核心的方向重新进栈,并走到新的位置。如果 有探测到x=m,y=n,则已达到迷宫得出口,可以停止检测,输出存在栈中的 路径:若在某一个位置的8个方向上都堵塞,则退回1步,继续探测,如果[程序实现] （1） 设计思想 当迷宫采用二维数组表示时，老鼠 在迷宫中任一时刻的位置可由数组的 行列序号 i,j 来表示。而从[i][j]位 置出发，可能的行进方向见下图 1。 如果[i][j]周围位置均为 0 值，则老 鼠可以选择这 8 个维之中的任一个作 为它的下一个位置。将这八个方向分 别记作：E（东）、SE（东南）、S（南）、 SW（西南）、W（西）、NW（西北）、N （北）和 NE（东北）。但是并非每一 个位置都有 8 个相邻位置。如果[i][j] 位于边界上，即 i=1,或 i=m,或 j=n,则相邻位置可能是 5 个或 3 个。为了避 免检查边界条件，将数组四周围用值为 1 的边框包围起来，这样二维数组 maze 应该声明为 maze[m+2][n+2]。 在迷宫中行进时，可能有多个行进方向可供选择，我们可以规定方向搜 索的次序是从东（E）沿顺时针方向进行。为了简化问题，规定[i][j]的下 一步位置坐标是[x][y]，并将这 8 个方向上的 x 和 y 坐标的增量预先放在一 个结构数组 move[8]中（见图 2）。该数组的每个分量有两个域 dx 和 dy。例 如要向东走，只要在 j 值上加 dy,就可以得到下一步位置的[x][y]的值为 [i][j+dy]。于是搜索方向的变化只是要令方向值 dir 从 0 增加到 7，便可 以从 move 数组中得到从[i][j]点出发搜索到的每一个相邻点[x][y]。 x=i+move[dir].dx y=j+move[dir].dy 为了防止重走原路，我们规定对已经走到过的位置，将原值 0 改为-1， 这既可以区别该位置是否已经走到过，又可以与边界值 1 相区别。当整个搜 索过程结束后，可以将所有的-1 该回到 0，从而恢复迷宫的原样。 这个计算机走迷宫的算法是：采取一步一步试探的方法。每一步都从东 （E）开始，按顺时针方向对 8 个方向进行探测，如某个方向上的 maze[x][y]=0,表示可以通行，则走一步；如 maze[x][y]=1,表示此方向上 不可通行，须换方向再试，直至 8 个方向都试过，maze[x][y]均为 1，说明 此步已无路可走，须退回一步，再上一步的下一个方向上重新探测。为此须 设置一个栈，用来记录所走过的位置和方向（i,j,dir）。当退回一步时，就 从栈中退回一个元素，以便在上一个位置的下一个方向上探测，如果有找到 一个进行方向，这把但前位置核心的方向重新进栈，并走到新的位置。如果 有探测到 x=m,y=n,则已达到迷宫得出口，可以停止检测，输出存在栈中的 路径；若在某一个位置的 8 个方向上都堵塞，则退回 1 步，继续探测，如果 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0