（1）迷宫问题
①问题描述
这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。
简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图1所示。
图1 迷宫示意图
迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。
②基本要求
-
设计迷宫的存储结构。
-
设计通路的存储结构。
-
设计求解通路的算法。
-
设计迷宫显示和通路的显示方式。
-
输入：迷宫、入口及出口可在程序中设定，也可从键盘输入。
-
输出：迷宫、入口、出口及通路路径。
③实现提示
-
存储设计
迷宫：以一个m×n的数组表示迷宫，如图3所示。数组元素0和1分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为1。
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
图2 迷宫存储示意图
方向：每一个可通点有4个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把4个方向上的位移存在一个数组中。如把东、南、西、北依次编号为0、1、2、3.其增量数组move[4]如图3所示。
|
move[4] |
x |
y |
|
1 |
1 |
0 |
|
2 |
0 |
1 |
|
3 |
-1 |
0 |
|
4 |
0 |
-1 |
图3 数组move[4]
通路：通路上的每一个点有3个属性：一个横坐标属性x、一个列坐标属性y和一个方向属性d，表示其下一点的位置。如果约定尝试的顺序为东、南、西、北，则每尝试一个方向不通时，d值增1，当d增至4时，表示此位置一定不是通路上的点，从栈中去除。在找到出口时，栈中保存的就是一条迷宫通路。
-
算法设计
要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步，重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探索前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探索。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。
寻找通路的算法思想如下：
Setp1：入口点坐标及到达该点方向（设为-1）入栈。
Step2：当栈不空时循环执行下列操作：
2.1 栈顶元素出栈至（x,y,d）。
2.2 按预设定顺序求出下一个要试探的方向d++，执行下述操作：
2.2.1 如果方向d可走，则：
2.2.1.1 将（x,y,d）入栈。
2.2.1.2 求新点坐标，得新（x,y）。
2.2.1.3 如果新点（x,y）是终点，则试探结束；
否则，置d=0。
2.2.2 否则，试探下一个方向，d++。
Setp3：栈空，表示没有通路；否则，出栈，得到通路路径。
④测试与运行
-
当迷宫数组为图3所示时，（1,1）为入口，（4,6）为出口，则可能的通路为：
通路1：（1,1）、（1,2）、（2,2）、（3,2）、（4,2）、（4,3）、（4,4）、（4,5）、（4,6）
通路2：（1,1）、（1,2）、（2,2）、（2,3）、（2,4）、（3,4）、（4,4）、（4,5）、（4,6）
通路3：（1,1）、（1,2）、（2,2）、（2,3）、（2,4）、（2,5）、（2,6）、（3,6）、（4,6） -
重设迷宫，使得没有通路，进行测试。
⑤思考
-
若每个点有8个试探方向（东、东南、南、西南、西、西北、北、东北），如何修改程序？
-
如何求得所有通路？
-
如何求得最短通路？
#include<iostream>
#include<string.h>
#include<cstdio>
using namespace std;
class Stack
{
public:
struct Node//栈里有三个变量和一个指针
{
int x;
int y;
int d;//方向
Node * next;
Node():next(NULL) {}
Node(int a,int b,int c):x(a),y(b),d(c),next(NULL) {}
};
int length;
Node * topOfStack;//栈顶指针
Stack(int a,int b ,int c)//构造函数 赋值
{
int length = 1;
Node * p = new Node(a,b,c);
topOfStack = p;
}
void push(int a,int b,int c)//入栈
{
Node * p = new Node(a,b,c);
p -> next = topOfStack;
topOfStack = p;
length ++;
}
void pop()//出栈
{
Node * p = topOfStack -> next;
delete topOfStack;
topOfStack = p;
length --;
}
void print()//打印
{
Node * p = topOfStack;
while(p !=NULL)
{
cout<<"("<<p->x<<","<<p->y<<")"<<endl;
cout<<"↑"<<endl;
p = p -> next;
}
}
bool isEmpty()//判断是不是空栈
{
if(topOfStack == NULL)return true;
else return false;
}
void Clear()//删除栈中元素
{
while(!isEmpty())
{
Node * p = topOfStack;
topOfStack = topOfStack -> next;
delete p;
p = topOfStack;
}
}
};
int main()
{
//freopen("in.cpp","r",stdin);
cout<<"please input m and n"<<endl;
int m,n;
while(cin>>m>>n)
{
int Map[m][n];
int road[m][n];//记录该节点是否被访问，0代表没访问过，1代表访问过
for(int i = 0 ; i < m ; i++)
{
for( int j = 0 ; j < n ; j++)
{
cin>>Map[i][j];
}
}
memset(road,0,sizeof(road));//对road清零处理
cout<<"entrance:"<<endl;
int entr[1][2];//入口坐标
cin>>entr[0][0]>>entr[0][1];
cout<<"exit:"<<endl;
int exit[1][2];//出口坐标
cin>>exit[0][0]>>exit[0][1];
int d[6]= {0,1,2,3,4,5}; //1左 2下 3右 4上
if((Map[entr[0][0]][entr[0][1]]==1)||(Map[exit[0][0]][exit[0][1]]==1))
{
cout<<"input error"<<endl;
continue;
}
Stack dusk(entr[0][0],entr[0][1],d[1]);//把入口坐标和方向1压入栈
road[entr[0][0]][entr[0][1]]=1;//入口坐标被访问
while((dusk.topOfStack->x != exit[0][0])||(dusk.topOfStack->y != exit[0][1]))
//当入口坐标和出口坐标的x，y有一个不一样就循环
{
if(dusk.topOfStack->d == d[1])//方向1
{
if(Map[dusk.topOfStack->x][dusk.topOfStack->y-1] == 0
&& dusk.topOfStack->x>=0
&& dusk.topOfStack->x<=m
&&dusk.topOfStack->y-1>=0
&&dusk.topOfStack->y-1<=n
&&road[dusk.topOfStack->x][dusk.topOfStack->y-1]==0)
//满足左边的节点没被访问、值为0、在n*m内，就把左边的节点压入栈
{
dusk.push(dusk.topOfStack->x,dusk.topOfStack->y-1,d[1]);
road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
}
else
{
//如果不满足，方向+1
dusk.topOfStack->d ++;
}
}
if(dusk.topOfStack->d == 2)
{
if(Map[dusk.topOfStack->x+1 ][dusk.topOfStack->y] == 0
&& dusk.topOfStack->x+1>=0 && dusk.topOfStack->x+1<=m
&&dusk.topOfStack->y>=0&&dusk.topOfStack->y<=n
&&road[dusk.topOfStack->x+1][dusk.topOfStack->y]==0
)
{
dusk.push(dusk.topOfStack->x+1,dusk.topOfStack->y,d[1]);
road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
}
else
{
dusk.topOfStack->d ++;
}
}
if(dusk.topOfStack->d == 3)
{
if(Map[dusk.topOfStack->x][dusk.topOfStack->y+1] == 0
&& dusk.topOfStack->x>=0 && dusk.topOfStack->x<=m
&&dusk.topOfStack->y+1>=0&&dusk.topOfStack->y+1<=n
&&road[dusk.topOfStack->x][dusk.topOfStack->y+1]==0)
{
dusk.push(dusk.topOfStack->x,dusk.topOfStack->y+1,d[1]);
road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
}
else
{
dusk.topOfStack->d ++;
}
}
if(dusk.topOfStack->d == 4)
{
if(Map[dusk.topOfStack->x-1][dusk.topOfStack->y] == 0
&& dusk.topOfStack->x-1>=0 && dusk.topOfStack->x-1<=m
&&dusk.topOfStack->y>=0&&dusk.topOfStack->y<=n
&&road[dusk.topOfStack->x-1][dusk.topOfStack->y]==0)
{
dusk.push(dusk.topOfStack->x-1,dusk.topOfStack->y,d[1]);
road[dusk.topOfStack->x][dusk.topOfStack->y]=1;
}
else
{
dusk.topOfStack->d ++;
}
}
if(dusk.topOfStack->d == 5)//如果四个方向都走不通，就出栈
{
dusk.pop();
}
if(dusk.topOfStack==NULL)//如果到不了
{
cout<<"can not arrive"<<endl;
break;
}
}
dusk.print();//打印
dusk.Clear();//初始化
cout<<"please input m and n"<<endl;
}
}