迷宫问题（C++）： 最短路径计算（队列）&& 路径输出（栈）（附一个易错点~）

迷宫问题大同小异，先直接上代码ba~：

#include<bits/stdc++.h> // 包含标准库头文件
using namespace std; // 使用标准命名空间
#define size 100 // 定义迷宫大小
typedef struct{ // 定义结构体STU
    int x, y;
}STU;
queue<STU>q; // 定义队列q

int n, bd[size][size]={0}, re_bd[size][size]={0}; // 定义迷宫大小n，迷宫数组bd和最短路径数组re_bd
int help[8][2] = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}}; // 定义八个方向的移动

int main()
{
	
	cin>>n; // 输入迷宫大小n
	for(int i=0; i<n; i++) // 循环读入迷宫
	{
		for(int j=0; j<n; j++)
		{
			cin>>bd[i][j];
		}
	}
	int sy, sx, ey, ex, flag=0; // 定义起点、终点和标志变量
	cin>>sy>>sx>>ey>>ex; // 输入起点和终点坐标
	re_bd[sy][sx] = 0; bd[sy][sx] = 1; // 初始化起点
	STU p, cur, f; p.y = sx; p.x = sy; // 初始化当前位置
	q.push(p); // 将起点入队
	while(!q.empty()) // 队列不空时循环
	{
		cur.y  = q.front().y;    cur.x  = q.front().x;    q.pop(); // 出队当前位置
		for(int i=0; i<8; i++) // 遍历八个方向
		{
			f.y = cur.y + help[i][0];    f.x = cur.x + help[i][1]; // 计算新位置
			
			if(bd[f.y][f.x] == 0) // 如果新位置可达
			{
				bd[f.y][f.x] = 1; // 标记新位置已访问
				q.push(f); // 新位置入队
				if(re_bd[f.y][f.x]==0) re_bd[f.y][f.x] = re_bd[cur.y][cur.x] + 1; // 更新最短路径值
			}
			else{
				continue; // 否则继续下一个方向
			}
			
			if(f.y == ey && f.x == ex) // 到达终点
			{
				printf("%d", re_bd[ey][ex]); // 输出最短路径长度
				flag = 1; break; // 设置标志并跳出循环
			}
		}
		if(flag == 1) break; // 如果已找到最短路径，跳出循环
	}
//被注释的代码可以输出re_bd的状态
//	for(int i=0; i<n; i++)
//	{
//		printf("\n");
//		for(int j=0; j<n; j++)
//		{
//			printf("%d ", re_bd[i][j]);
//		}
//		
//	}
	if(flag == 1) // 如果找到最短路径
	{
		stack<STU>s; // 定义栈s
		s.push(f); // 将终点入栈
		while(1) // 循环找到起点
		{
			cur.y = s.top().y; cur.x = s.top().x; // 获取栈顶元素
			if(cur.y == sy && cur.x == sx) break; // 到达起点，跳出循环
			for(int i=0; i<8; i++) // 遍历八个方向
			{
				f.y = cur.y + help[i][0]; 
				f.x = cur.x + help[i][1]; // 计算新位置
				int org = re_bd[cur.y][cur.x] - 1; // 原路径值
				int now = re_bd[f.y][f.x]; // 当前路径值
				if(org == 0) // 如果是起点
				{
					if(f.y == sy && f.x == sx) // 如果是起点
					{
						s.push(f); break; // 将起点入栈并跳出循环
					}
					continue; // 否则继续下一个方向
				}
				if( org == now && org != 0) // 如果是最短路径
				{
					s.push(f); break; // 将当前位置入栈并跳出循环
				} 
			}
			
 		}
 		printf("\n"); // 换行
 		for(; !s.empty(); ) // 输出路径
 		{
		 	printf("%d, %d; ", s.top().y, s.top().x); // 输出当前位置
		 	s.pop(); // 出栈
		 }
	}
	return 0; // 返回
}

易错点在于最短路径的回溯过程

回溯路径的原理：从出口开始，在re_bd（PS: re_bd[ i ][ j ]用来记忆从起点到第 i 行第 j 列的最短路径长度）里找周围八个方向中路径长度少1的点， 故一般情况可用以下代码非注释部分来判断

int org = re_bd[cur.y][cur.x] - 1; // 原路径值
int now = re_bd[f.y][f.x]; // 当前路径值
//if(org == 0) // 如果是起点
//{
//	if(f.y == sy && f.x == sx) // 如果是起点
//	{
//		s.push(f); break; // 将起点入栈并跳出循环
//	}
//	continue; // 否则继续下一个方向
//}
if( org == now && org != 0) // 如果是最短路径
{
	s.push(f); break; // 将当前位置入栈并跳出循环
} 

但是！ 当要去寻找起点时，re_bd(起点) = 0！而且周围没有被走过的点都在一开始因为被初始化， 也全都是0！如此，则根本没有办法保证能成功找到起点。

解决方式：

1.补充上面被注释掉的“if(org == 0) // 如果是起点”部分， 将起点单独讨论

2.或者“见好就收”， 在re_bd == 1 时就结束寻找，在printf栈元素之前先print一下起点坐标

~如果对你有启发，还请点个赞告诉笔者哈~

关于re_bd的状态， 可以用加上下面的代码自行输出看看~

    for(int i=0; i<n; i++)
	{
		printf("\n");
		for(int j=0; j<n; j++)
		{
			printf("%d ", re_bd[i][j]);
		}
		
	}

~都看到这啦， 你一定是个超级认真的友友，关注一下吧~