数字迷宫思考-下
-----用递归的方法实现数字迷宫
数字迷宫，可以用栈和递归的方法实现。通常情况下，递归都比较容易实现，因此，试着用递归的方法来实现数字迷宫游戏。虽然递归相对比较简单，但是，当递归次数较多时，可能会造成代码空间的增大；另外，在最后显示通路路径的时候，存在一个问题：显示只能从出口到入口倒着显示路径信息，这是不方便的。不过，将递归当着一种方法来解决问题，也是值得尝试的。下附上数字迷宫的c++实现源代码。
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//Node.h
#ifndef NODE_H
#define NODE_H
//坐标偏移及方向
struct offset
{
int a,
b;
char* dir;
};
#endif
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//Maze.h
#ifndef MAZE_H
#define MAZE_H
#include"Node.h"
//路径搜索函数
bool pathSearch(int sx,int sy,int Maze[][10],int Mark[][10],int ex,int ey);
#endif
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//Maze.cpp
#include"Maze.h"
#include<iostream>
#include<cstdlib>
using namespace std;
bool pathSearch(int sx,int sy,int Maze[][10],int Mark[][10],int ex,int ey)
{
offset move[8]={{-1,0,"N"},{-1,1,"NE"},{0,1,"E"},{1,1,"SE"},{1,0,"S"},{1,-1,"SW"},{0,-1,"W"},{-1,-1,"NW"}};
if(sx==ex && sy==ey)
{
//输出出口节点
cout<<"("<<sx<<","<<sy<<","<<move[4].dir<<")"<<endl;
return true;
}
int g,h;
char* d;
for(int i=0;i<8;i++)
{
g=sx+move[i].a;
h=sy+move[i].b;
d=move[i].dir;
if(Maze[g][h]==0 && Mark[g][h]==0)
{
Mark[g][h]=1;
if(pathSearch(g,h,Maze/*[][10]*/,Mark/*[][10]*/,ex,ey))//注意这里的引用方式
{
cout<<"("<<sx<<","<<sy<<","<<d<<")"<<endl;
return true;
}
}
}
if(sx==1 && sy==0)
cout<<"没有路径!"<<endl;
Mark[1][0]=1;
return false;
}
/**********************************************************
Copyright@2009-2011 by hank(SiChuan University)
***********************************************************/
//main.cpp
#include"Maze.h"
#include<iostream>
using namespace std;
int main()
{
int m=10,
p=10;
int Mark[10][10];
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
Mark[i][j]=0;
int Maze[10][10]={{1,1,1,1,1,1,1,1,1,1},
{0,0,0,1,1,0,1,1,0,1},{1,1,1,0,0,1,1,0,1,1},{1,1,0,1,1,0,0,1,1,1},
{1,0,1,1,0,1,1,0,1,1},{1,1,0,1,1,1,1,1,0,1},{1,0,1,1,0,1,0,0,1,1},
{1,0,1,0,1,1,1,1,1,1},{1,1,0,1,0,0,0,1,1,1},{1,1,1,1,1,1,1,0,1,1}};
cout<<"***************迷宫阵型图**************"<<endl;
for(int ii=0;ii<10;ii++)
{
for(int jj=0;jj<10;jj++)
cout<<Maze[ii][jj]<<" ";
cout<<endl;
}
int sx=1,
sy=0,
qr=9,
qc=7;
cout<<"******从出口到入口逆向显示路径:*******"<<endl;
bool out=pathSearch(sx,sy,Maze,Mark,qr,qc);
cout<<endl;
cout<<"*************显示走过的路径***********"<<endl;
for(int k=0;k<10;k++)
{
for(int m=0;m<10;m++)
cout<<Mark[k][m]<<" ";
cout<<endl;
}
cout<<"***************测试结束***************"<<endl;
return 0;
}