java - 将二维矩阵转换为图形

Question

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

这样的二维矩阵

# # # # #
# . 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:
  shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

Answer 1

字符的二维矩阵是该问题的完美图形表示。

每个矩阵元素 (i,j) 都是一个节点。假设你只能向东、西、北、南步进，从这个节点到它的邻居(i+or-1，j+or-1)存在 0 到 4 条无向边，这是通过简单地测试每个位置的字符来确定的。

您还可以测试超出范围(负数或太大)的 i,j 值，但如果如您所示，边界周围总是有一堵“墙”，则不需要这样做。这堵墙用作sentinel .

构建通用结构来表示嵌入网格中的图形是浪费时间和内存。