说明
老鼠走迷宫是递回求解的基本题型.我们在二维阵列中使用 2 表示迷宫墙壁,使用 1 来表示老鼠的行走路径,尝试以程式求由入口至出口的路径.
解法
老鼠可走上,下,左,右四个方向.入口一般在左上,出口在右下(如果说有其他出入口情况则下述老鼠每步默认选择方向的顺序改变)
老鼠从入口出发,每走一步进行一次四个方向的选择,判断下步是否有可走方向(由于入口在左上,出口在左下,则优先选择右,下方向,之后选择左,上方向).无法前进时退回上步选择下一个可前进方向.
如此在阵列中按照顺序测试四个方向,直到走出出口为止.
代码(c语言版,思路可参考)
参数声明
int maze[7][7] = { {2,2,2,2,2,2,2},
{2,0,0,0,0,0,2},
{2,0,2,0,2,0,2},
{2,0,0,2,0,2,2},
{2,2,0,2,0,2,0},
{2,0,0,0,0,0,2},
{2,2,2,2,2,2,2} };//mazing map
int(*mazeP)[7];
mazeP = maze;//将二维数组传递给数组指针(数组指针是指针指向一个数组)
int startI = 1, startJ = 1, endI = 5, endJ = 5;//entrance and exit
int success = 0;//success 无辜的芒果
int i = 1,j = 1;//initialization of import and export
复制代码递回方法
//递回进行老鼠每步选择的方向,返回是否成功
int mazing_visit(int i, int j,int(*mazeP)[7],int success)
{
mazeP[i][j] = 1;
if (i == 5 && j == 5)success = 1;
//优先右下,然后左上
if ( 1 != success && mazeP[i][j + 1] == 0)mazing_visit(i, j + 1, mazeP, success);
if (success != 1 && mazeP[i + 1][j] == 0)mazing_visit(i + 1, j, mazeP, success);
if (success != 1 && mazeP[i][j - 1] == 0)mazing_visit(i, j - 1, mazeP, success);
if (success != 1 && mazeP[i - 1][j] == 0)mazing_visit(i - 1, j, mazeP, success);
if (success != 1)mazeP[i][j] == 0;
return success;
}
复制代码完整代码
#include
#include
#include
//Mazing-老鼠走迷宫
int mazing_visit(int, int,int (*p)[7],int);
void mazing()
{
int maze[7][7] = { {2,2,2,2,2,2,2},
{2,0,0,0,0,0,2},
{2,0,2,0,2,0,2},
{2,0,0,2,0,2,2},
{2,2,0,2,0,2,0},
{2,0,0,0,0,0,2},
{2,2,2,2,2,2,2} };//mazing map
int(*mazeP)[7];
mazeP = maze;//将二维数组传递给数组指针(数组指针是指针指向一个数组)
int startI = 1, startJ = 1, endI = 5, endJ = 5;//entrance and exit
int success = 0;//success 无辜的芒果
int i = 1,j = 1;//initialization of import and export
printf("显示迷宫: n");
for (i = 0; i < 7; i++)
{
for (j = 0; j < 7; j++)
{
if (mazeP[i][j] == 2)//判断是否是墙壁
{
printf("*");
}
else
{
printf(" ");
}
}
printf("n");
}
//判断是否存在出口,若有出口则打印出路径
if (mazing_visit(startI, startJ, mazeP,success) == 0)
{
printf("n没有找到出口n");
}
else
{
printf("n显示路径:");
for (i = 0; i < 7; i++)
{
for (j = 0; j < 7; j++)
{
if (mazeP[i][j] == 2)
{
printf("*");
}
else if (mazeP[i][j] == 1)
{
printf(">");
}
else
{
printf(" ");
}
}
printf("n");
}
}
}
int mazing_visit(int i, int j,int(*mazeP)[7],int success)
{
mazeP[i][j] = 1;
if (i == 5 && j == 5)success = 1;
//优先右下,然后左上
if ( 1 != success && mazeP[i][j + 1] == 0)mazing_visit(i, j + 1, mazeP, success);
if (success != 1 && mazeP[i + 1][j] == 0)mazing_visit(i + 1, j, mazeP, success);
if (success != 1 && mazeP[i][j - 1] == 0)mazing_visit(i, j - 1, mazeP, success);
if (success != 1 && mazeP[i - 1][j] == 0)mazing_visit(i - 1, j, mazeP, success);
if (success != 1)mazeP[i][j] == 0;
return success;
}
int main(void)
{
mazing();
return 0;
}
复制代码