从二维数组创建邻接矩阵

Question

我有一个如下所示的数组：

a b c d 
e f g h
j k l m
n o p q

我的想法是从中创建一个仅用于水平和垂直移动的邻接矩阵，其中成本是目标中的 ASCII 值。

解决方案将找到以下类型的邻接矩阵（简化的'a'=1）：

  a b c d e f g h <- start
a 0 1 0 0 1 0 0 0 
b 2 0 2 0 0 2 0 0
c 0 3 0 3 0 0 3 0 
d 0 0 4 0 0 0 0 4
e 5 0 0 0 0 5 0 0
f 0 6 0 0 6 0 6 0
g 0 0 7 0 0 7 0 7
h 0 0 0 8 0 0 8 0
^ destination

为简洁起见，我删除了原始矩阵的最后两行。我已经意识到一行只有一个特定的成本，并且最多有 4 个邻接。我的问题是如何找到这些邻接？如果可能的话，我只想遍历原始矩阵，以免自己使用呈指数增长的邻接矩阵。

Answer 1

与所有好的问题一样，我需要一些笔和纸。解决方案似乎是以下代码，其中 'M' 是原始矩阵， 'adj' 是生成的具有维度 x 和 y 的邻接矩阵：

makeAdjacencyMatrix(M,adj)
  for row = 0 .. y do
    for col = 0 .. x do
      val = M[row,col]
      loc = row * x + col
      above = loc - x
      below = loc + x
            
      if loc + 1 < x * y then
        adj[loc, loc + 1] = val
      if loc - 1 >= 0 then
        adj[loc, loc - 1] = val
      if above >= 0 then
        adj[loc, above] = val;
      if below < x * y then
        adj[loc, below] = val

  return adj

我会尽可能将问题标记为已回答。

从二维数组创建邻接矩阵

Creating adjacency matrix from 2D array

algorithm

adjacency-matrix