C++实现迷宫最短路径 |21xrx.com

C++实现迷宫最短路径

2023-06-29 19:27:41 深夜i -- --

C++ 迷宫最短路径算法图论

迷宫是一种经典的游戏，其中一个重要的问题是如何找到从起点到终点的最短路径。在计算机科学领域，使用C++语言来实现迷宫最短路径是一个非常受欢迎的问题，因为它涉及到算法、数据结构、图论等多个方面。

要实现迷宫最短路径，需要先将迷宫表示为一个图。具体来说，每个迷宫单元格表示一个图节点，单元格之间的墙壁表示两个节点之间不存在边。然后，可以使用搜索算法（如深度优先搜索或广度优先搜索）来确定从起点到终点的最短路径。

在实现算法时，需要建立一个图数据结构。可以使用邻接矩阵或邻接表来表示图。通常情况下，使用邻接表表示图的效率更高。

例如，以下是使用邻接表表示迷宫的C++代码：


#include <iostream>
#include <vector>
using namespace std;
const int N = 100;
// 定义邻接表节点结构体
struct Node w;
;
// 定义图类
class Graph {
public:
  vector<Node> adj[N]; // 邻接表数组
  int n; // 图中节点数目
  Graph(int n)
    this->n = n;
  
  // 添加一条边
  void add_edge(int u, int v, int w) {
    adj[u].push_back( w);
    adj[v].push_back( w);
  }
};
// 解析迷宫字符串
vector<string> parse_maze(string s) {
  vector<string> res;
  string row;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == '\n') {
      res.push_back(row);
      row.clear();
    } else {
      row.push_back(s[i]);
    }
  }
  if (!row.empty()) {
    res.push_back(row);
  }
  return res;
}
// 将迷宫转换成图
Graph maze_to_graph(vector<string> maze) {
  int n = maze.size();
  int m = maze[0].size();
  Graph g(n*m); // 总共n*m个节点
  // 定义节点编号函数，将2D坐标转换成1D编号
  auto index = [=](int i, int j) {
    return i*m + j;
  };
  // 添加边
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (maze[i][j] == '#') continue; // 墙壁不是节点
      // 如果不是最后一列，则向右连一条边
      if (j < m-1 && maze[i][j+1] != '#') {
        g.add_edge(index(i, j), index(i, j+1), 1);
      }
      // 如果不是最后一行，则向下连一条边
      if (i < n-1 && maze[i+1][j] != '#') {
        g.add_edge(index(i, j), index(i+1, j), 1);
      }
    }
  }
  return g;
}
// 计算从起点到终点的最短路径
int shortest_path(Graph& g, int s, int t) {
  vector<int> dist(g.n, INT_MAX); // 距离数组，初始值为正无穷
  vector<bool> vis(g.n); // 标记数组，用来存储节点是否访问过
  dist[s] = 0; // 起点距离为0
  // 不停地找距离起点最近的未访问节点，并更新它的邻居节点的距离
  while (!vis[t]) {
    int u = -1, min_dist = INT_MAX;
    for (int i = 0; i < g.n; i++) {
      if (!vis[i] && dist[i] < min_dist) {
        u = i;
        min_dist = dist[i];
      }
    }
    if (u == -1) break; // 无法到达终点
    vis[u] = true;
    for (auto& e : g.adj[u]) {
      if (!vis[e.v]) {
        dist[e.v] = min(dist[e.v], dist[u]+e.w);
      }
    }
  }
  return (vis[t] ? dist[t] : -1);
}
int main() {
  string s = "\
    #####\n\
    #  #\n\
    ### #\n\
    #  #\n\
    #####";
  vector<string> maze = parse_maze(s);
  int n = maze.size();
  int m = maze[0].size();
  Graph g = maze_to_graph(maze);
  int s = 0, t = n*m-1;
  cout << shortest_path(g, s, t) << endl; // 输出最短路径长度
  return 0;
}

这段代码首先定义了一个`Node`结构体，作为邻接表节点的一部分。然后，定义了`Graph`类，其中包含了一个邻接表数组`adj`和节点数目`n`。接下来是一些公共函数，如解析迷宫字符串、将迷宫转换成图等。最后定义了主函数，它调用上述所有功能来计算从起点到终点的最短路径长度。在本例中，迷宫被硬编码为一个字符串，但实际上可以通过文件输入或网络传输等方式来获取迷宫。

上一篇: idea打包java可执行jar包

下一篇: 谭浩强的C++程序设计第三版

评论区

()

相似文章