哈工大数据结构大作业 - 迷宫老鼠

一、 问题描述

一个迷宫可用上图所示方阵[m,n]表示，0表示能通过，1 表

示不能通过。现假设老鼠从左上角[1,1]进入迷宫，编写算法，寻 求一条从右下角[m,n] 出去的路径。

入口出口0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 1 0 0

0 0 0 0 0 1 1 1 0 0

二、 方法思路

1.关于迷宫

1.1迷宫用而为动态数组实现。maze[i,j](1≤i≤m, 1≤j≤n)，maze是m行n列的迷宫，为了消除边界判断，把二维数组maze[1:m][1:n]扩大为maze[0:m+1][0:n+1]，且令0行、0列、m+1行、m+1列的值为1，表示周围是围墙。

1.2起点maze[1][1]置0，终点maze[m-2][n-2]置0。

2.主导思想

2.1.判断走下一步的依据是在迷宫的范围内坐标是否为空。压栈以记录行走路线。

2.2若走到死路，则弹栈进入上一步，再次判断周围是否有可走位置。

3.具体算法 3.1如果四周有路

if(w[ii-1][jj]*w[ii+1][jj]*w[ii][jj-1]*w[ii][jj+1]==0)，则老鼠按照下右左上的次序进行选择，如果满足空的条件，则压栈，并将走过的路线置2. if(0==w[ii+1][jj]) {

Push(ii,jj,Q);w[ii][jj]=2; ii++; }

else if(0==w[ii][jj+1]) {

Push(ii,jj,Q);w[ii][jj]=2; jj++; }

else if(0==w[ii][jj-1]) {

Push(ii,jj,Q);w[ii][jj]=2; jj--; } else {

Push(ii,jj,Q);w[ii][jj]=2; ii--;

3.2.若起点四周都没路，或返回至起点四周没路 else

if(w[ii-1][jj]+w[ii+1][jj]+w[ii][jj-1]+w[ii][jj+1]==4)，则结束程序。

3.3 若走入死路,回溯,栈中元素数-1,移动回来的格

Pop(Q);ct--; w[ii][jj]=1; if(-1==w[ii+1][jj]) { ii++; }

else if(-1==w[ii][jj+1]) { jj++; }

else if(-1==w[ii][jj-1]) { jj--; } else { ii--; } }// }

3.4.找到一条通路后，将元素逆序压入另一个新栈以便打印通路。 三、主要数据结构及源程序代码及其注释