c语言实现老鼠走迷宫
在没有智能手机的时代,不少人玩游戏会玩老鼠走迷宫这样的闯关游戏。每一关有着不同的地图场景,可能还会充斥着各种障碍。
- 老鼠走迷宫是经典的递回求解的算法题
我们用二维数组表示迷宫场景。其中用2代表迷宫的墙壁,0代表可行通道。
我们用7*7的二维数组具体实现,假定我们设置[1][1]是迷宫入口,[5][5]是迷宫出口。
#define M 7
int maze[M][M] =
{
{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,2},
{2,0,0,0,0,0,2},
{2,2,2,2,2,2,2}
};
int start1=1,start2=1;
int end1=5,end2=5;
int main ()
{
int i,j;
printf("显示迷宫:\n");
for(i=0;i<M;i++) //对摆放的数组迷宫进行打印
{
for(j=0;j<M;j++)
if(maze[i][j] == 2)
printf("◾");
else
printf(" ");
printf("\n");
}
}
这样我们的迷宫绘制基本完成。下面我们对老鼠可能行走的路径进行分析输出。
我们定义一个visit函数,对老鼠行走方向进行逻辑分析。我们把老鼠走的路径记作1,也就是数组中的0被改为1 。
int success = 0; //声明全局变量,若到达出口,将被赋值为1
int visit(int i,int j)
{
maze[i][j] = 1; //传过来的位置一定是老鼠所行路径,赋值为1
if(i==end1 && j==end2) //判断是否到达[5][5]出口位置
success = 1;
//判断是否到达出口,没有则分析老鼠可以在迷宫移动的方向,并递归求下一步.
if(success != 1 && maze[i][j+1] == 0) //老鼠先尝试向右,如果可行就递归,不行则往下判定
visit(i,j+1);
if(success != 1 && maze[i+1][j] == 0) //老鼠尝试向下,如果可行就递归,不行则往下判定
visit(i+1,j);
if(success != 1 && maze[i][j-1] == 0) //老鼠尝试向左,如果可行就递归,不行则往下判定
visit(i,j-1);
if(success != 1 && maze[i-1][j] == 0) //最后一歩方向判定,老鼠尝试向上,如果可行就递归。
visit(i-1,j);
//判断是否到达出口,没有则证明前面走的路径并不能到达出口,那么返回,把走过的位置重新写作0
if(success != 1)
maze[i][j] = 0;
return success;
}
我们写好老鼠的行走路径后,在主函数中调用,并且输出。
以下代码写在主函数中
if(visit(start1,start2) == 0) //调用visit函数,判断老鼠是否走出迷宫
printf("\n没有找到出口!\n");
else{
printf("\n显示路径:\n");
for(i=0;i<M;i++)
{
for(j=0;j<M;j++)
{
if(maze[i][j] == 2) //当值为2时是墙壁
printf("◾");
else if(maze[i][j] == 1) //当值为1时是路径
printf("