数据结构回溯法的应用之迷宫最短路径问题

Stephenie ·

更新时间:2024-11-13

· 582 次阅读

/ 回溯法倒是不难理解，大家可以叫我迷宫大师了 /

题目

A maze is to be represented by a 12*12 array composed of three values: Open, Wall, or Exit. There is one exit from the maze. Write a program to determine whether it is possible to exit the maze from the starting point (any open square can be a starting point). You may move vertically and horizontally to any adjacent open square(左右上下四个方向). You may not move to a square containing a wall. The input consists of a series of 12 lines of 12 characters each, representing the contents of each square in the maze. The characters are O, W, or E.

【输入】 12×12的迷宫方阵，每个格子的可能取值有：O, W, or E，输入数据能够确保迷宫只有一个出口。
任意3个起点的坐标,格式如下(x,y)。其中x为纵坐标，y为横坐标，起始坐标从左上角的格子开始，坐标起始值为0.

【输出】
起点到出口的最短路径长度（经过多少个方格），若起点无法到达出口则输出-1。起始节点和结束节点都算入路径长度的计算。

例如：
【输入】
O W O W O W O O W O W O
O W O W W W W O W O O E
O W W W O O O O O O O O
W W W O O O O W W W O W
O O O O W W W O O O O O
O O W O W O W O W O W W
O W W O O O W W O O O W
O O W O O W W W O O O O
O O O W O O O O W W W W
W W W O O O O W W W O O
O W W W W O O O O O W W
W W W O O O O O W W W W
(0,0) (5,7) (7,8)

【输出】
-1 9 10

【解释】
输出表示第一个点（0，0）无法到达出口；
第二个点（5，7）到达出口的最短路径是9；
第三个点（7，8）到达出口的最短路径是10；

解题思路

首先构造一个maze类，成员函数里面包含迷宫的创建，清理和读取步数，把棋盘、步数和出口坐标作为成员变量。棋盘大小限定了是12*12，为了不考虑出界，我们认为加上边界，即将棋盘存在14*14的数组里。之后读取棋盘，设置为两种状态，1是墙，不能走，0是通路可以走。这都是很基础的。

然后就是关键的回溯法走迷宫。先将当前点设置为1，即不可通行状态，然后再递归调用函数，分别向上下左右四个方向出发，返回上一级函数的时候再将那个点重置为0。

base case有两个，一是此路不通，直接返回上层节点；二是走到终点，将所用步数（递归调用树深度）和原步数比较，存小的那个。

不过个人感觉这样做的效率挺低，还存在一定的优化空间。

ac代码

#include 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
class Maze
{
	public:
		Maze();//初始化 
		void createmaze();//创建迷宫 
		void solve(int x,int y,int cnt);//走迷宫 
		int getstep();//获取步数 
		void init();//初始化 
	private:
		int maze[14][14];
		int tempmaze[14][14];
		int step;//步数 
		int ox,oy;//出口坐标 
};
Maze::Maze()
{
	step=10000;
}
void Maze::init()
{
	step=10000;
}
void Maze::createmaze()
{
	char opr;
	for(int i=0;i<14;i++)
	{
		maze[0][i]=maze[i][0]=maze[13][i]=maze[i][13]=1;
	}
	for(int i=1;i<13;i++)
	{
		for(int j=1;j> opr;
			if(opr=='W')
				maze[i][j]=1;
			else if(opr=='O')
				maze[i][j]=0;
			else
			{
				maze[i][j]=0;
				ox=i;
				oy=j;
			}
		}
	}
}
void Maze::solve(int x,int y,int cnt)
{
	if(maze[x][y]!=0) //此路不通
		return;
	if(x==ox&&y==oy)//走出迷宫
	{
		step=min(cnt,step);
		return;
	}
	maze[x][y]=1;
	//四个方向探索 
	if(x>=1)
		solve(x-1,y,cnt+1);
	if(y<=12)
		solve(x,y+1,cnt+1);
	if(x=1)
		solve(x,y-1,cnt+1);
	maze[x][y]=0;
	return; 
}
int Maze::getstep()
{
	return step;
}
int main(int argc, char** argv) 
{
	Maze a;
	a.createmaze();
	for(int i=0;i> c >> x >> c >> y >> c;
	 	a.solve(x+1,y+1,0);
	 	if(a.getstep()==10000)
	 		cout << "-1" << " ";
	 	else
	 		cout << a.getstep()+1 << " ";
	}
	return 0;
}