#include<string.h>
#include<stdlib.h>
#include<time.h>
int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag
void maze()
{
int i,j
time_t t
srand(time(&t))
for(i=0i<mi++)
for(j=0j<nj++)
{
map[i][j]=rand()%2
if(map[i][j])
num++
}
if(num<m*n/2)
{
for(i=0i<mi++)
for(j=0j<nj++)
if(!map[i][j])
map[i][j]+=rand()%2
}
map[0][0]=1
map[m-1][n-1]=1
}
void print()
{
int i,j
for(i=0i<mi++)
for(j=0j<nj++)
{
printf("%d ",map[i][j])
if(j==n-1)puts("")
}
}
void dfs(int x,int y)
{
int i,tx,ty
if(!flag)
return
for(i=0i<4i++)
{
tx=x+d[0][i]
ty=y+d[1][i]
if(!f[tx][ty]&&tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty])
{
f[tx][ty]=1
a[ans]=tx
b[ans++]=ty
if(tx+ty==0)
{
printf("(%d,%d)\n",m,n)
for(flag=i=0i<ansi++)
printf("(%d,%d)\n",a[i]+1,b[i]+1)
return
}
dfs(tx,ty)
f[tx][ty]=0
ans--
}
}
}
int main()
{
while(scanf("%d%d",&m,&n),m+n)
{
memset(f,0,sizeof(f))
num=ans=0
flag=1
maze()
print()
dfs(m-1,n-1)
if(flag)
puts("There is no path")
}
return 0
}
本程序的前提是将迷宫保存在一个二维数组里，可走的地方为0，不可走的地方为1。由于采用回朔算法，不使用递归，所以首先应该建立一个栈来保存路径，路径是用一个一个点来表示的，也就是说栈中保存的是一系列点的列表。栈节点类型说明：
struct StackNode
{
POINT Point
struct StackNode *Next, *Prev//双向链表形式
}
栈结构用一个类（CPointStack）实现，声明如下：
class CPointStack
{
public:
void ClearStack()//清空栈
void InitStack()//初始化栈
bool Pop(POINT &pt)//弹出顶端元素，并给出该点的坐标，返回是否弹出成功
bool Push(POINT pt)//将pt点的信息压入栈，返回是否压入成功
CPointStack()
virtual ~CPointStack()
protected:
StackNode *m_psnTop//栈顶指针
StackNode m_snBottom//栈底，不保存点信息
}
以下为成员函数实现，都是一些数据结构的操作，应该没什么好说的：
//构造时初始化栈
CPointStack::CPointStack()
{
InitStack()
}
//析构时清空栈
CPointStack::~CPointStack()
{
ClearStack()
}
//将点压入栈(成功返回true,失败返回false)
bool CPointStack::Push(POINT pt)
{
StackNode* NewNode = new StackNode
//是否返回true主要看这里申请内存是否成功
if(!NewNode)
return false
NewNode->Point = pt
NewNode->Prev = m_psnTop
NewNode->Next = NULL
m_psnTop->Next = NewNode
m_psnTop = NewNode
return true
}
//将点弹出栈(成功返回true,栈为空则返回false)
bool CPointStack::Pop(POINT &pt)
{
if(m_psnTop == &m_snBottom)//是否返回true主要看这里栈是否为空
return false
StackNode *p
p = m_psnTop
m_psnTop = m_psnTop->Prev
pt = p->Point
delete p
m_psnTop->Next = NULL
return true
}
//初始化栈
void CPointStack::InitStack()
{
m_psnTop = &m_snBottom
m_snBottom.Next = NULL
m_snBottom.Prev = NULL
}
//清空栈
void CPointStack::ClearStack()
{
StackNode *p
while(m_psnTop != &m_snBottom)
{
p = m_psnTop
m_psnTop = m_psnTop->Prev
delete p
}
}
接下来设计怎样走出这个迷宫，也就是迷宫算法的主体部分。再次用一个类实现。
在设计这个类时，我考虑到以下几点：
1、迷宫入口和出口的坐标
2、保存迷宫的2维数组
3、获得路径的函数
但是实际设计时由于没有考虑太多问题，只是以设计迷宫算法和解决一个具体迷宫为目的，所以没有考虑动态大小的迷宫，而是将迷宫大小定为601×401。而且在设计迷宫算法后没有将路径顺序输出而是直接在原图中标识（在保存迷宫数据的表中设置经过的点为2而将死路点设置为3）。
这样迷宫类（CGoMaze）的声明为：
class CGoMaze
{
public:
void Go()//寻找路径的函数
POINT m_ptIn//入口坐标
POINT m_ptOut//出口坐标
BYTE m_btArrMaze[401][601]//保存迷宫的二维表
CGoMaze()
virtual ~CGoMaze()
}
最后让我们来看一下CGoMaze::Go()这个函数：
我们模仿人走迷宫时的思路，设置一个当前点，一个目标点（下一个要走的点）。初始情况下当前点为入口，终止条件为当前点为出口，这样，我们的函数大概结构就出来了。
在从入口到出口的过程中程序对当前点的上、下、左、右四个点依次进行判断，当发现任一个方向是未走过的区域时，就将当前点指向那个点进行尝试，同时将当前点入栈并做标记。而当4个方向都不通或已走过时，则为死路，标记当前点为死路并从栈中弹出上一个点继续进行尝试，这时因为当前点已被标记为死路，则弹出上一个点时就不会重复这条路，达到寻找正确路径的效果。
Go函数的具体实现如下，其实挺简单的^_^：
void CGoMaze::Go()
{
CPointStack psPath//保存路径的栈
POINT ptCur = m_ptIn, ptNext//设置当前点为入口
while(ptCur.x != m_ptOut.x || ptCur.y != m_ptOut.y)//判断是否已经走出
{
ptNext = ptCur//设置目标点为当前点，便于下面偏移
if(m_btArrMaze[ptCur.y - 1][ptCur.x] == 0)
ptNext.y --//如果上方是空的，则目标点向上偏移
else if(m_btArrMaze[ptCur.y][ptCur.x - 1] == 0)
ptNext.x --//如果左边是空的，则目标点向左偏移
else if(m_btArrMaze[ptCur.y + 1][ptCur.x] == 0)
ptNext.y ++//如果下方是空的，则目标点向下偏移
else if(m_btArrMaze[ptCur.y][ptCur.x + 1] == 0)
ptNext.x ++//如果右边是空的，则目标点向右偏移
else
{//这里是没有路的状态
m_btArrMaze[ptCur.y][ptCur.x] = 3//标记为死路
psPath.Pop(ptCur)//弹出上一次的点
continue//继续循环
}
//如果有路的话会执行到这里
m_btArrMaze[ptCur.y][ptCur.x] = 2//标记当前点为路径上的点
psPath.Push(ptCur)//当前点压入栈中
ptCur = ptNext//移动当前点
}
}
其实这个部分可以将栈设置为CGoMaze类的成员，然后在Go函数里加上：
psPath.ClearStack()
这样就可以用Timer来演示走迷宫的过程了
#include "graphics.h"#include "stdio.h"
#define N 10
#define M N*N-4+1 /*堆栈最大值，用来保存路口信息*/
#define UP 1
#define DOWN -1
#define LEFT 2
#define RIGHT -2
#define UP_M man.x-1>=0&&a[man.x-1][man.y] /*人当前位置的上一个位置*/
#define DOWN_M man.x+1<N&&a[man.x+1][man.y]
#define LEFT_M man.y-1>=0&&a[man.x][man.y-1]
#define RIGHT_M man.y+1<N&&a[man.x][man.y+1]
#define ENTER 3 /*岔路的入口*/
#define HAVE 2 /*某条路已经走过*/
struct cross across,stack[M]=
int top=1
int PX=70,PY=40
struct man
/*迷宫定义，1表示路，可自行更改迷宫的路径，可使全为1，看效果等*/
int a[N][N]={0,0,0,1,1,0,1,1,1,0,
1,1,0,1,0,1,1,0,1,0,
0,1,1,1,1,0,1,1,1,1,
1,0,1,0,1,1,1,0,1,0,
1,1,1,1,0,0,1,1,1,1,
1,0,1,0,1,1,1,0,1,0,
0,0,1,1,1,0,1,1,1,0,
1,1,1,0,1,0,1,0,1,0,
0,0,1,0,1,1,1,0,1,1,
0,1,1,0,0,1,0,0,0,0}
void init_man()/*初始化人的状态，要求迷宫入口须在左侧*/
{int isetcolor(WHITE)
for(i=0i<Ni++)
if(a[i][0]) {man.x=iman.y=0
if(a[i][1]) man.s=RIGHT
else if(i+1<N&&a[i+1][0]) man.s=DOWN
else if(i-1>=0&&a[i-1][0]) man.s=UP
else
return }
if(i==N)
}
void show_map() /*显示迷宫*/
{int i,j
for(i=0i<Ni++)
for(j=0j<Nj++)
if(a[i][j]) {setfillstyle(1,WHITE)
bar(PX+j*20,PY+i*20,PX+j*20+20,PY+i*20+20)}
else {setfillstyle(1,LIGHTBLUE)
bar(PX+j*20,PY+i*20,PX+j*20+20,PY+i*20+20)}
setcolor(BLACK)
for(i=0i<Ni++)
{line(PX+i*20,PY,PX+i*20,PY+20*N)
line(PX,PY+i*20,PX+20*N,PY+i*20)}
}
void show_man(int color)
{
setfillstyle(1,color)
bar(PX+man.y*20+5,PY+man.x*20+5,PX+man.y*20+20-5,PY+man.x*20+20-5)
}
int cross()/*岔路判断*/
{int count=0
if(UP_M) count++
if(DOWN_M) count++
if(LEFT_M) count++
if(RIGHT_M) count++
return count}
void move()/*依据人的移动状态而移动到新位置*/
{
show_man(GREEN)
switch(man.s)
{case UP:man.x-=1break
case DOWN:man.x+=1break
case LEFT:man.y-=1break
case RIGHT:man.y+=1break
}
show_man(LIGHTRED)
}
void back() /*回头走*/
{switch(man.s)
{case UP:man.s=DOWNmove()break
case DOWN:man.s=UPmove()break
case LEFT:man.s=RIGHTmove()break
case RIGHT:man.s=LEFTmove()break
}
}
void go_on() /*为通路且不是岔路时，继续向前走*/
{switch(man.s)
{case UP:if(UP_M) move()
else if(LEFT_M)
else if(RIGHT_M)
break
case DOWN:if(DOWN_M) move()
else if(LEFT_M)
else if(RIGHT_M)
break
case LEFT:if(LEFT_M) move()
else if(UP_M)
else if(DOWN_M)
break
case RIGHT:if(RIGHT_M) move()
else if(UP_M)
else if(DOWN_M)
break
}
}
int xin() /*判断人当前位置是否是新岔路口*/
{int i
for(i=1i<topi++)
if(man.x==stack[i].x&&man.y==stack[i].y) return i
return 0
}
void copy() /*拷贝岔路信息到across结构体*/
{across.x=man.x
across.y=man.y
if(UP_M==1) across.up=1
elseacross.up=0
if(DOWN_M==1) across.down=1
else across.down=0
if(LEFT_M==1) across.left=1
else across.left=0
if(RIGHT_M==1) across.right=1
else across.right=0
}
void rukou() /*为岔路设置一个入口*/
{switch(man.s)
{case UP:across.down=ENTERbreak
case DOWN:across.up=ENTERbreak
case LEFT:across.right=ENTERbreak
case RIGHT:across.left=ENTERbreak
}
}
void xuanlu(struct cross *p)/*在岔路时，为人选一条路行走*/
{switch(man.s)
{case UP:if(p->up==1) p->up=HAVE
else if(p->left==1)
else if(p->right==1)
else
break
case DOWN:if(p->down==1) p->down=HAVE
else if(p->left==1)
else if(p->right==1)
else
break
case LEFT:if(p->left==1) p->left=HAVE
else if(p->up==1)
else if(p->down==1)
else
break
case RIGHT:if(p->right==1) p->right=HAVE
else if(p->up==1)
else if(p->down==1)
else
break
}
}
push(struct cross *p) /*把新岔路口入栈*/
{stack[top].left=p->left
stack[top].right=p->right
stack[top].up=p->up
stack[top].down=p->down
stack[top].x=p->x
stack[top].y=p->y
top++
}
int wan(struct cross *p) /*当前人所在的岔路口走完否？*/
{int count=0
if(p->left==1) count++
if(p->right==1) count++
if(p->up==1) count++
if(p->down==1) count++
if(count>0) return 0
return 1
}
void chukou(struct cross *p)/*人从出口出来*/
{if(p->up==ENTER) man.s=UP
else if(p->down==ENTER) man.s=DOWN
else if(p->left==ENTER) man.s=LEFT
else man.s=RIGHT
}
main()
{int c,k
int gdriver=DETECT,gmode
registerbgidriver(EGAVGA_driver)
initgraph(&gdriver,&gmode,"")
cleardevice()
show_map()
init_man()show_man(LIGHTRED)getch()delay(65000)
do{
switch(c=cross())
{case 1:switch(man.s)
{case UP:if(UP_M) move()
else back()break
case DOWN:if(DOWN_M) move()
else back()break
case LEFT:if(LEFT_M) move()
else back()break
case RIGHT:if(RIGHT_M) move()
else back()break}
break
case 2:go_on()break
case 3:
case 4:k=xin()
if(!k)
else {if(wan(&stack[k])) chukou(&stack[k])
else xuanlu(&stack[k])}
move()
break
}
delay(65000)
}while(!kbhit())
closegraph()}
==================================================
编译环境：tc 2.0
