#include <iostream.h>
#include <conio.h>
const int m = 9;
const int n = 9;
const
int maze[m+2][n+2] = {{0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,1,0,1,0,0},
{0,0,1,0,0,1,0,1,1,0,0},
{0,0,0,1,0,0,1,0,0,0,0},
{0,0,1,0,0,0,1,0,0,0,0},
{0,0,0,1,0,1,0,1,0,0,0},
{0,0,0,0,1,0,0,1,0,0,0},
{0,0,1,0,1,0,1,0,0,0,0},
{0,0,0,1,0,0,0,1,1,0,0},
{0,0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0,0}};
typedef
struct node
{ int ipos,jpos; // 表示路径上某点的位置
int direct[8]; // 表示周围8个方向的可能探索信息
struct node *next; // 指向前一个栈结点
}node_type; // 探索路径时使用的链栈结点类型
typedef
struct postp
{ int ipos,jpos;
struct postp *next;
}pos_type; // 回溯路径时使用的链栈的结点类型
node_type *top; // 指向探索栈栈顶的指针
pos_type *pos_top; // 指向路径栈栈顶的指针
void init() // 初始化探索栈
{ top=new node_type;
top->ipos=1;
top->jpos=1;
top->direct[0]=maze[0][0];
top->direct[1]=maze[0][1];
top->direct[2]=maze[0][2];
top->direct[3]=maze[1][0];
top->direct[4]=maze[1][2];
top->direct[5]=maze[2][0];
top->direct[6]=maze[2][1];
top->direct[7]=maze[2][2];
top->next=NULL;
}
void check_cycle(int ii, int jj, node_type *newp) // 确认当前位置周围某点为不可探索
{ node_type *p=top;
while((p!=NULL)&&(!((p->ipos==ii)&&(p->jpos==jj)))) // 遍历栈
p=p->next; // 确认该点是否已入栈
if(p!=NULL)
switch(newp->ipos-ii)
{ case 1: switch(newp->jpos-jj)
{ case 1: newp->direct[0]=0; break;
case 0: newp->direct[1]=0; break;
case -1: newp->direct[2]=0;
}
break;
case 0: switch(newp->jpos-jj)
{ case 1: newp->direct[3]=0; break;
case -1: newp->direct[4]=0;
}
break;
case -1: switch(newp->jpos-jj)
{ case 1: newp->direct[5]=0; break;
case 0: newp->direct[6]=0; break;
case -1: newp->direct[7]=0;
}
}
}
void push(int ii, int jj) // 前进一步时的入栈
{ node_type *p;
p=new node_type;
p->ipos=ii;
p->jpos=jj;
p->direct[0]=maze[ii-1][jj-1];
p->direct[1]=maze[ii-1][jj];
p->direct[2]=maze[ii-1][jj+1];
p->direct[3]=maze[ii][jj-1];
p->direct[4]=maze[ii][jj+1];
p->direct[5]=maze[ii+1][jj-1];
p->direct[6]=maze[ii+1][jj];
p->direct[7]=maze[ii+1][jj+1];
check_cycle(ii-1,jj-1,p);
check_cycle(ii-1,jj,p);
check_cycle(ii-1,jj+1,p);
check_cycle(ii,jj-1,p);
check_cycle(ii,jj+1,p);
check_cycle(ii+1,jj-1,p);
check_cycle(ii+1,jj,p);
check_cycle(ii+1,jj+1,p);
p->next=top;
top=p;
}
void pop() // 排除当前点的出栈
{ node_type *p;
p=top;
top=p->next;
delete p;
}
void show_maze() // 显示迷宫
{ int i,j;
cout<<"The maze is showed as below (1 --- possible pathway): \n";
for(i=1; i<m+1; i++)
{ cout<<" ";
for(j=1; j<n+1; j++) cout<<maze[i][j]<<' ';
cout<<endl;
}
}
void show_pathway() // 显示走出迷宫的路径
{
初始化路径栈;
当探索栈非空, 重复下列操作
{
将探索栈顶出栈的点信息写入新建的路径栈结点;
}
当路径栈非空, 重复下列操作
{
输出路径栈栈顶出栈的点信息;
}
}
void main()
{ int i;
show_maze();
init();
while((top!=NULL)&&(!((top->ipos==m)&&(top->jpos==n))))
{ for(i=0; i<8; i++)
if(top->direct[i]==1)
{ top->direct[i]=0;
break;
}
switch(i)
{ case 0: push(top->ipos-1,top->jpos-1); break;
case 1: push(top->ipos-1,top->jpos); break;
case 2: push(top->ipos-1,top->jpos+1); break;
case 3: push(top->ipos,top->jpos-1); break;
case 4: push(top->ipos,top->jpos+1); break;
case 5: push(top->ipos+1,top->jpos-1); break;
case 6: push(top->ipos+1,top->jpos); break;
case 7: push(top->ipos+1,top->jpos+1); break;
default: pop();
}
}
if(top!=NULL)
{ cout<<"The pathway is: \n";
show_pathway();
}
else
cout<<"There is no pathway through the maze.\n";
getch();
}