BFS求最短路径

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <string>
#include <queue>
#include<stack>
using namespace std;
#define maxn 100
struct node
{
	int x, y;
	int step;
};
node Node,A,B;
int n, m;
char maze[maxn][maxn];
bool inq[maxn][maxn] = { false };
int X[4] = {0,0,1,-1};
int Y[4] = {1,-1,0,0};
stack<node> Vis;
stack<node> path;
bool judge(int x, int y)//函数用于判断什么样的元素需要压入队列中
{
	if (x >= n || x<0 || y>=m || y < 0)
		return false;
	if (maze[x][y] == 'x' ||inq[x][y] == 1)
		return false;
	return true;
}
int BFS()
{
	queue<node> Q;
	Q.push(A);
	while (!Q.empty())
	{
		node top = Q.front();
		Q.pop();//take one element and erase on at the same time;
		//cout << top.step<<" (" << top.x <<","<< top.y<<") " << endl;
        inq[top.x][top.y] = true;
		if (top.x == B.x && top.y == B.y)
		{
			return top.step;
		}
		Vis.push(top);
		for (int i = 0; i < 4; i++)
		{
			int newx = top.x + X[i];
			int newy = top.y + Y[i];
			int newStep = top.step + 1;
			if (judge(newx, newy) == 1)
			{
				inq[newx][newy] = true;
				Node.x = newx;
				Node.y = newy;
				Node.step = newStep;
				Q.push(Node);
			}
		}
	}
	return -1;
}
void ThePath()
{
	node P = Vis.top();
	path.push(P);
	int t = P.step;
	Vis.pop();
	while (!Vis.empty())
	{
		if (P.x == Vis.top().x && (P.y == Vis.top().y + 1 || P.y == Vis.top().y - 1))
		{
			P.y = Vis.top().y;
			path.push(P);
			Vis.pop();
		}
		else if (P.y == Vis.top().y && (P.x == Vis.top().x + 1 || P.x == Vis.top().x - 1))
		{
			P.x = Vis.top().x;
			path.push(P);
			Vis.pop();
		}
		else
			Vis.pop();
	}
}
int main()
{
	cout << "输入这是几乘几的迷宫:" << endl;
	cin >> n >> m;
	//for (int x = 0; x <= n; x++)
	//	cin.getline(maze[x], m + 2);//不能这样写：在输入一个字符数组后会自带一个'\0'即NULL，这样写就是先有'\n'再自动一个NULL了
	cout << "输入你的迷宫:" << endl;
	for (int i = 0; i < n; i++)
	{
		cin.get();//vital skill
		for (int j = 0; j < m; j++) {
			maze[i][j] = cin.get();
		}
		//maze[i][m + 1] = '\0';//自带
	}
	A.step = 0;
	cout << "分别输入起点、终点的坐标 ：" << endl;
	cin >> A.x >> A.y;
	cin >> B.x >> B.y;
	cout <<"最短路径的长度是："<< BFS()<<endl;
	ThePath();
	cout << "最短路径是："<<endl;
	while (!path.empty())
	{
		cout <<" ("  <<path.top().x<<"," << path.top().y<<") " << endl;
		path.pop();
	}
}