小编Vir*_*rat的帖子

我在将包含无效点和有效点的给定二维矩阵转换为只有有效节点的图形时遇到问题。问题是这样的。我有一个二维矩阵

# # # # #
# . C C #
# S # # #
# . . E #
# # # # # 

我想找到从 S 到 E 的最短距离，记住我必须覆盖所有的 'C' 和 '#' 作为一堵墙和 '.' 充当自由路径。现在我想将此矩阵转换为仅包含有效节点的图形。请帮帮我。

n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
 for k=1 to n:
   for i=1 to n:
    for j=1 to n:
        d[i][j] = min(d[i][j], d[i][k] + d[k][j])

shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes: …