Question

关于计算机C++编程的迷宫问题的解题思路？

答案若满意追加100分！

Answer 1

/*走通用迷宫问题的思路是：从给定的任意一个起点开始，向各个方向都有走动的可能，按照一定的顺序进行。
判断如果该方向上能走，（能走要是：不是以前走过的地方，不是墙壁，不是地图之外）就走这一步，然后记录下这一步。
如果不能走，就换下一个方向，如果能走就继续下一步。各个方向都不能走，说明到了死路，这时候就返回上一步去走下一个方向。如此继续。
每走动一步都要检测是不是到达目标了，如果到达就输出结果。
如果不能走到目标，返回到最除起点也不能走了，说明无解。
我的示意程序如下：
*/
/*地图路径求解程序，用VC++编写的，*/
#include<stdio.h>
#include<stdlib.h>
#define
ROW
9/*定义行数*/
#define
COL
13/*定义列数*/
typedef
struct
RowAndColPath{
int
r;
int
c;
}RowAndColPath;/*定义结构体实现走步过程的记录*/
int
Move[4][2]={{0,1},{1,0},{-1,0},{0,-1}};/*4个方向*/
RowAndColPath
path[ROW*COL];/*走动过程的记录*/
bool
ResultFlag=false;/*找到解的标志*/
bool
GettingPath(int
step,int
CurrentRow,int
CurrentCol,int
ResultRow,int
ResultCol,int
MapWay[][COL]);/*递归求解方法*/
void
main()
{
int
MapWay[ROW][COL]={
{1,1,1,1,1,1,1,1,0,1,1,1,1},
{0,0,0,1,1,0,0,0,0,1,1,1,1},
{1,1,0,1,1,1,1,1,0,0,1,1,1},
{1,1,0,0,0,0,1,1,1,0,1,1,1},
{1,1,0,1,1,0,0,0,0,0,0,0,1},
{1,1,0,0,1,1,1,1,1,1,1,0,1},
{1,1,1,0,0,0,0,0,0,1,1,0,1},
{1,1,1,0,1,1,1,1,0,0,0,0,1},
{1,1,1,0,0,0,1,1,1,1,1,1,1}};/*定义地图*/
int
CurrentRow=1,CurrentCol=0,ResultRow=0,ResultCol=8;/*定义初始和结束位置*/
path[0].r=CurrentRow;
path[0].c=CurrentCol;/*初始位置进入历史的第一步*/
if(GettingPath(1,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay))/*如果走动成功*/
printf("恭喜！查找成功！\n");
else
printf("抱歉，查找失败！\n");
}
bool
GettingPath(int
step,int
CurrentRow,int
CurrentCol,int
ResultRow,int
ResultCol,int
MapWay[][COL])
{
int
i,j;
for(i=0;i<4;i++)/*依次对4个方向搜索*/
{
if(ResultFlag)
return
true;
CurrentRow+=Move[i][0];
CurrentCol+=Move[i][1];/*先按该方向前进一步*/
if((CurrentRow>=0)&&(CurrentRow<ROW)&&(CurrentCol>=0)&&(CurrentRow<COL))/*如果还在地图内部*/
{
if(MapWay[CurrentRow][CurrentCol]==0)/*下一步可以走*/
{
for(j=0;j<step;j++)/*判断是不是重复了以前走过的路*/
{
if((path[j].r==CurrentRow)&&(path[j].c==CurrentCol))
break;
}
if(j==step)/*如果没有走过这个点，就走*/
{
path[step].r=CurrentRow;
path[step].c=CurrentCol;/*计入该步*/
step++;
if((CurrentRow==ResultRow)&&(CurrentCol==ResultCol))/*如果已到达目的地*/
{
ResultFlag=true;
printf("路径如下：\n\n");
for(j=0;j<step;j++)
printf("第
%d
步：\t%d\t%d\n",j,path[j].r,path[j].c);
return
true;
}
else
{
if(step>=ROW*COL)/*如果已经走遍了地图，就宣布失败*/
return
0;
if(!ResultFlag)
GettingPath(step,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay);/*没有到达目的，继续走*/
}
}
else/*如果已经走过这一点，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
else/*如果该点不可走，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
else/*如果该步出地图了，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
if(ResultFlag)
return
true;
return
false;/*无路可走*/
}