一.题目:
用一个m行n列的二维数组来表示迷宫。数组中每个元素的取值为0或1。其中值0表示通路,值1表示阻塞,迷宫的入口在左上放(1,1)处,出口在右下方(m,n)处。要求求出从迷宫入口到出口有无通路,若有通路则指出其中一条通路的路径,即输出找到通路的迷宫数组,其中通路上的“0”用另外一个数字8替换,同时打印出所走通路径上每一步的位置坐标及下一步的方向。
二.算法说明:
(1)以二维数组maze[m][n]表示迷宫,并设maze[1][1]处为迷宫入口,maze[m][n]处为迷宫出口,迷宫中的任一位置以maze[i][j]来表示。
(2)对于迷宫中的每个位置(i,j)处,可能移动的路线可以有八个方向,用一个二维数组move表示这八个方向上坐标的增量,并把这八个方向从正东起按顺时针方向编上序号,则
move[k][0]表示第k个方向上i的增量,
move[k][1]表示第k个方向上j的增量。
move数组的方向增量表内容如下:k 1 2 3 4 5 6 7 8
int move[8][2]={ {0,1}, //正东 i不变 j+1 向右
{1,1}, //右下 i+1 j+1
{1,0}, //下 i+1 j不变
{1,-1}, //
{0,-1}, //
{-1,-1}, //
{-1,0}, //
{-1,1}}; //
(3)当处于迷宫边缘时,它的下一个位置不再有八种可能,甚至只有三种可能。所以,为了简化边界位置的检测,将二维数组maze[m][n]扩充到maze[m+2][n+2],且令其四周边界位置的值均为1。
(4)计算机解迷宫,要用一步一试探的方法。为此在开始每一步时,都要从正东方向起,沿顺时针方向检测。当探测到某个方向上下一个位置的值为0时,就沿着此方向走一步,当这一步周围剩下的七个方向的上的值均为1时,则退回一步重新检测下一方向。在这过程中,建立一个mark[m+2][n+2]数组来记录某位置是否走过,走过用1记,未走过用0记。据此,可以用递归的思路来解决该问题。
(5)具体的算法可以概括如下:
走迷宫过程中,如果当前位置(i,j)(初始以入口为当前位置)已到达出口,即(i,j)=(m,n),则说明已找到一条通路,返回值1,表示走通,结束递归过程;
如果当前位置的各个方向上都没有找到通向出口的路径,则递归返回值0,表示未走通,若此时的位置在入口处,给出“没有通路”的信息,结束递归;
如果对当前位置的各个方向依次试探的过程中,发现某个方向的试探位置可以走(即maze与mark数组中该位置的值均为0),则把试探位置作为调用参数递归调用走迷宫过程,同时对调用的返回值进行判断,若调用返回值为1,则表示当前位置在走通的路径上,因此要记录下该位置,且递归返回1。
在记录走通的每步位置时,考虑到递归的特点,若要正序打出走通的路径,我们则可以另入口和出口颠倒,即可实现目的。
三,源码
#include <iostream>
using namespace std;
const int m=12,n=15;//迷宫的大小
int maze[m+2][n+2]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,//输入迷宫地图
1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,
1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,
1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,
1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,
1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,
1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,
1,0,0,1,1,0,1,1,1,0,1,0,0,1,1,1,1,
1,0,1,1,1,1,0,0,1,1,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,1,1,0,0,0,1,1,0,1,1,0,0,0,1,0,1,
1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,
1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
int mark[m+2][n+2];//设立迷宫是否走过标志
int move[8][2]={{0,1}, //正东 i不变 j+1 向右
{1,1}, //右下 i+1 j+1
{1,0}, //下 i+1 j不变
{1,-1}, //
{0,-1}, //
{-1,-1}, //
{-1,0}, //
{-1,1}}; //
//方向指标
int SeekPath(int x,int y)
{
int i,g,h;
if(x==1&&y==1) //如果到终点则找到路径,返回 1
return 1;
for (i=0;i<8;i++)//尝试每一个方向
{
g=x+move[i][0];
h=y+move[i][1]; //探索地点的新坐标
if(maze[g][h]==0&&mark[g][h]==0)//如果该地点走得通且没有被探索过
{
mark[g][h]=1;//将这一地点置为探索过
if(SeekPath(g,h))//从这一地点开始新的探索,如果成功
{
cout<<"("<<g<<","<<h<<")";//则打出这一点的坐标
if(move[i][0]==1) cout<<"North->";
if(move[i][0]==-1) cout<<"South->";
if(move[i][1]==1) cout<<"West->";
if(move[i][1]==-1) cout<<"East->";//判断前一地点到这一地点的方向
cout<<endl;
maze[g][h]=8;//把这一点设为通路
return 1;//返回1
}
}
}
if(x==m&&y==n)
cout<<"No path!"<<endl;//如果最后回到了起点,则说明没有通路
return 0;//返回0
}
int main()
{
int i,j;
for (i=0;i<m+2;i++)
for (j=0;j<n+2;j++)
mark[i][j]=0;//先将所有通路置为没有走过
mark[m][n]=1;//将起点置为走过了
if(SeekPath(m,n)) //如果走通
{
cout<<"("<<m<<","<<n<<")"<<endl;//先打出起点坐标
maze[m][n]=8;//将起点设为通路
for (i=0;i<m+2;i++)
for (j=0;j<n+2;j++)
{
cout<<maze[i][j]<<" ";
if(j==n+1)
cout<<endl;
}//打印出走通后的迷宫
}
}
分享到:
相关推荐
老鼠走迷宫,用数组跌打计算。 老鼠走迷宫,用数组跌打计算。
C++语言的老鼠走迷宫的算法,用栈实现,可以算出最短路径,功能强大
由于迷宫的设计,老鼠走迷宫的入口至出口路径可能不只一条,如何求出所有的路径呢? (可先下载我上传的《C经典算法之老鼠走迷宫(一)》看,然后再看这个)
数据结构经典算法他全 如 河内之塔 三色旗 老鼠走迷宫 八皇后等等
说明:老鼠走迷宫是递回求解的基本题型,我们在二维阵列中使用2表示迷宫墙壁,使用1来表示老鼠的行走路径,试以程式求出由入口至出口的路径。 解法:老鼠的走法有上、左、下、右四个方向,在每前进一格之后就选一个...
智能老鼠走迷宫算法,很经典,有拓展性,适合算法狂人
【原创】小老鼠走迷宫算法的java实现,具体的分析在我的csdn blog中有详细说明。
vc6编译器编译,C语言写的代码,老鼠走迷宫,用广度优先的寻找最短的路径算法,遍历全部路径使用的是深度算法。完整代码可直接下载调试运行。
算法课做的,经典问题老鼠走迷宫,需要的同学可以参考
主要介绍了Python基于递归算法实现的走迷宫问题,结合迷宫问题简单分析了Python递归算法的定义与使用技巧,需要的朋友可以参考下
老鼠走迷宫程序实例。C语言程序、希望对大家有帮助
智能老鼠走迷宫算法的设计让我们轻松学习智能老鼠走迷宫算法的设计。
老鼠走迷宫源程序 (C#实现有图形界面还可加载地图) 自己写的 写了2天 运行时 先阅读 Readme。txt C# 大作业
qt实现老鼠走迷宫游戏(迷宫生成算法、深度优先、广度优先寻路算法)
电老鼠走迷宫算法.doc
迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法
演示一只老鼠如何走过一个特定迷宫,单路径
程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向健操纵老鼠在规定的时间内走到粮仓处。 基本要求: ⑴老鼠形象可以辨认,可用键盘操纵老鼠上下左右...
迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法迷宫算法
这是我在网络上看到的一个用A*算法写的走迷宫程序,拿出来跟大家一块分享作者的作品。