mar*_*cog 6 algorithm graph-theory
我们希望在特殊网格中找到两点之间的最短路径.我们可以在一次移动中在相邻的方块之间移动,但是我们也可以在一次移动中在相同类型的单元格之间移动(有10种类型),无论它们之间的距离如何.
我们如何才能找到在两个点之间行进所需的步数,最大尺寸为100x100？
创建 10 个数组，每个数组包含相应类型的单元格。现在运行Dijkstra（或BFS），但是当您访问类型为 的单元格时i，将所有类型为 的单元格添加i到队列中并清除相应的数组。这样你就不必访问相同类型单元格之间的每条边，并且复杂度为 O(n^2) 而不是 O(n^4)