将二维矩阵转换为图形

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 值，但如果如图所示边界周围始终存在“墙”，则不需要这样做。墙壁充当哨兵。

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

Answer 2

我要么创建一个节点结构，要么创建一个节点类。例如：

struct Node {
    node type;  //Indicate in some way if the node is a 'S', '.' or 'E'
    std::vector<Node> adjacentNodes;
}

至于填充这个数据结构，我将从“S”块开始。并进行类似于以下的递归调用：

Set alreadyVisited;

FillGraph(i,j,Node){
//    for all adjacent nodes, add them to Node's adjacentNodes.
//    add Node to alreadyVisited Set
//    for each of the adjacentNodes (i.e. any neighbor that isn't a wall.
//       if(adjacentNode is not in alreadyVisited)
//          FillGraph(adjaent-i, adjacent-j, adjacentNode);
}