迷宫最短路径（C++）_c++走迷宫最短路径

作者：运维做开发 | 2024-08-05 09:16:58

踩

c++走迷宫最短路径

迷宫最短路问题

接上次经典迷宫问题
问题：这次迷宫问题不仅要求判断是否能够找到通路，并且要求找到最短能到达迷宫所需的步数，即最短路径问题

暴力算法：对每个结点进行遍历，记录每种路径的步数；
优化剪枝：当遍历步数大于ans之前第一次找到ans初始化值为无穷大，当第一次找到通路路径后，ans被第一次step替换。之后的每次路径只要比前一次step小，就会被step小的替代；
剪枝：而在寻找通路的过程中，只要步数大于了前一次所找通路的step，这次寻找终止，返回下一次寻找；

代码如下：

#include <stdio.h>
#include <iostream>
using namespace std;
char Map[50][50];
int n,m,p,q,vis[50][50],ans,flag;
const int N=1000;
int dir[4][2]={
   {
   -11
2
3
4
5
6
7
8

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/931778