课程设计迷宫问题的求解

下面是好好范文网小编收集整理的课程设计迷宫问题的求解，仅供参考，欢迎大家阅读！

问题及要求：迷宫问题的求解包括以下功能：

对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。迷宫求解详细要求如下:

(1) 可以用一个m×n的二维数组表示迷宫，0和1分别表示迷宫中的通路和障碍。

(2) 该迷宫可以预先设定，也可以随机生成，或是根据提示设定,m,n均不小于20。

(3) 编写一个求解迷宫的程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。

(4) 迷宫求解通常用的是“穷举求解“方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

(5) 要求应用栈的特点完成迷宫求解。

代码实现：

#include<iostream>#include<cstdlib>#include<stdlib.h>#include<cstdio>#include<time.h>#define Max_Size 1000using namespace std;int m,n;int flag=1;enum Direcation {//迷宫中要走的方向，对应映射值    Up = 1,    Down = 2,    Left = 3,    Right = 4};typedef struct {//迷宫中坐标（x,y）	int x, y;} Coordinate;typedef struct {//定义当前点的坐标，以及接下来要走的方向	Coordinate coord;	Direcation direcation;} Node;class Stack {//定义一个栈的类，模拟栈的实现	public:		Stack();		bool IsEmpty() const;//判断栈是否为空		bool IsTopful() const;//判断栈是否满了		bool Push(Node Pushed);//入栈		bool Pop();//出栈		const Node& GetTop() const;//获取栈顶坐标点		void Output() const;//输出坐标信息	private:		Node stack[Max_Size];//定义坐标点 个数为最大值		unsigned int top;};Stack::Stack() {	top = 0;}bool Stack::IsEmpty() const {	return (top == 0);}bool Stack::IsTopful() const {	return (top == Max_Size + 1);}bool Stack::Push(Node Pushed) {	if (IsTopful())		return false;	else {		stack[top] = Pushed;		top++;		return true;	}}bool Stack::Pop() {	if (IsEmpty())		return false;	else {		top--;		return true;	}}const Node& Stack::GetTop() const {	return stack[top - 1];}void Stack::Output() const {	for (unsigned int inset = 0; inset < top; inset++) {//将所有合法形成的路径输出		cout << "("<<stack[inset].coord.x + 1 << "," << stack[inset].coord.y + 1 << ",";		switch (stack[inset].direcation) {			case Up:				cout << "Up)";				break;			case Down:				cout << "Down)";				break;			case Left:				cout << "Left)";				break;			case Right:				cout << "Right)";				break;			default:				cout << "Unknow";		}		cout << endl;	}	printf("(%d,%d,出口)",m,n);	cout << endl;	return;}void Check(const bool MAZE[25], bool MARK[25], Stack &wizard, Coordinate coord);//检查当前坐标点是否合法void OutputMaze(const bool MAZE[25]);//输出迷宫地图const Coordinate Origin = { 0, 0 }, Terminal = { m-1, n-1 };//确定起始点和终止点int main() {	Stack wizard;	Coordinate coord = Origin;	printf("*********************走迷宫*********************n");	printf("                 1.自定义迷宫 n");	printf("                 2.自动生成迷宫 n");	printf("                 3.退出 n");	printf("*********************请选择*********************n");	int choice;	bool MAZE[25][25]; //迷宫地图	scanf("%d",&choice);	if(choice==3)		return 0;	cout<<"请输入迷宫行数和列数：n";	bool MARK[25][25];	cin>>m>>n;	cout<<"请输入迷宫数据：n";	if(choice==1) {		for(int i=0; i<m; ++i) {			for(int j=0; j<n; j++) {				scanf("%d",&MAZE[i][j]);				MARK[i][j]=1;			}		}	} else if(choice==2) {		for(int k=0; k<m; k++)			for(int j=0; j<n; j++) {				int i;				i = rand()%2*1000;				MAZE[k][j]=i;				MARK[k][j]=1;			}	}	MAZE[0][0]=0;	MAZE[m-1][n-1]=0;	cout<<"迷宫地图显示.n";	OutputMaze(MAZE);	cout<<"回溯过程:"<<endl;	Check(MAZE, MARK, wizard, coord);	if(!flag) {		cout<<endl<<"可行路径："<<endl;		wizard.Output();	}	system("pause");	return 0;}void Check(const bool MAZE[25], bool MARK[25], Stack &wizard, Coordinate coord) {	Node now;	MARK[coord.x][coord.y] = false;//标记当前点已遍历过	if (coord.x == m-1&&coord.y == n-1)		return;//1.看是否到达终点,到就返回，不到继续遍历	if (MARK[coord.x - 1][coord.y] && MAZE[coord.x - 1][coord.y] == 0) { //如果合法，向上遍历		now.coord = coord;		flag=0;		now.direcation = Up;//2.记录当前点可行		wizard.Push(now);//3.把当前点压入栈中		cout<<"("<<now.coord.x+1<<","<<now.coord.y+1<<",";		switch (now.direcation) {			case Up:				cout << "Up)n";				break;			case Down:				cout << "Down)n";				break;			case Left:				cout << "Left)n";				break;			case Right:				cout << "Right)n";				break;			default:				cout << "Unknow";		}		coord.x--;//4.将当前点向上走一步。		Check(MAZE, MARK, wizard, coord);//5.进入下一次判断	} else if (MARK[coord.x][coord.y - 1] && MAZE[coord.x][coord.y - 1] == 0) { //如果合法，向左遍历		now.coord = coord;		flag=0;		now.direcation = Left;		wizard.Push(now);		cout<<"("<<now.coord.x+1<<","<<now.coord.y+1<<",";		switch (now.direcation) {			case Up:				cout << "Up)n";				break;			case Down:				cout << "Down)n";				break;			case Left:				cout << "Left)n";				break;			case Right:				cout << "Right)n";				break;			default:				cout << "Unknow"<<endl;		}		coord.y--;//向左走一步		Check(MAZE, MARK, wizard, coord);	} else if (MARK[coord.x][coord.y + 1] && MAZE[coord.x][coord.y + 1] == 0) { //如果合法，向右遍历		now.coord = coord;		flag=0;		now.direcation = Right;		wizard.Push(now);		cout<<"("<<now.coord.x+1<<","<<now.coord.y+1<<",";		switch (now.direcation) {			case Up:				cout << "Up)"<<endl;				break;			case Down:				cout << "Down)"<<endl;				break;			case Left:				cout << "Left)"<<endl;				break;			case Right:				cout << "Right)"<<endl;				break;			default:				cout << "Unknow";		}		coord.y++;//向右走一步		Check(MAZE, MARK, wizard, coord);	} else if (MARK[coord.x + 1][coord.y] && MAZE[coord.x + 1][coord.y] == 0) { //如果合法，向下遍历		flag=0;		now.coord = coord;		now.direcation = Down;		wizard.Push(now);		cout<<"("<<now.coord.x+1<<","<<now.coord.y+1<<",";		switch (now.direcation) {			case Up:				cout << "Up)n";				break;			case Down:				cout << "Down)n";				break;			case Left:				cout << "Left)n";				break;			case Right:				cout << "Right)n";				break;			default:				cout << "Unknow";		}		coord.x++;//向下走一步		Check(MAZE, MARK, wizard, coord);	} else {		if(coord.x==0&&coord.y==0) {			flag=1;			cout<<"无解n";			return ;		}		coord = wizard.GetTop().coord;//2.碰壁了，取上一个合法坐标向下一个方向试探		wizard.Pop();//3.上一个合法点出栈		Check(MAZE, MARK, wizard, coord);//4.接着下一个方向试探	}	return;}void OutputMaze(const bool MAZE[25]) {	for (int inset = 0; inset < m; inset++) {		for (int inset1 = 0; inset1 < n; inset1++) {			if (MAZE[inset][inset1])//迷宫如果坐标点是 1 ，输出 1				cout << "1 ";			else				cout << "0 ";//如果迷宫坐标点是 0 ，输出 0		}		cout << endl;	}	cout << endl;}