c++ - 我怎样才能找到从a[x][y]到任何a[v][w]的最短路径？

Question

我有这样的东西。

---a-

aaa--

一个----

---a-

b--a-

我怎样才能以最少的步骤到达b中的所有a？ 我该如何用图表来解决这个问题？

Answer 1

a* algorithm可能会很好地为您服务。它的变化是在游戏开发中寻找最短(成本最低的路径)的常见解决方案。至于图表示，定义一个称为节点和连接的结构。您可以使用 std::vector 来存储顶点，使用 std::vector 来存储连接(边)。

typedef struct 
{
  std::string name;
  //Other data that You need.
}Node;

typedef struct
{
  Node* nodeA;
  Node* nodeB;
  int travelCost;
  //other data that may come in handy
}Connection;

std::vector<Node> nodes;
std::vector<Connection> nodeConnections;