课程设计：迷宫问题的求解

问题及要求： 迷宫问题的求解包括以下功能：
  对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。迷宫求解详细要求如下:
(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 1000
using 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;
}