通过 R 中的方向矩阵进行回溯

我有一个这样的矩阵：

https://i.stack.imgur.com/mzeRI.png https://i.stack.imgur.com/mzeRI.png

你可以像这样加载它：

matrix = structure(c("-", "-", "C", "G", "C", "A", "-", "0", "V", "V", 
"V", "V", "C", "H", "D", "V", "DV", "V", "A", "H", "H", "D", 
"DV", "D", "C", "H", "DH", "DH", "D", "V", "G", "H", "H", "D", 
"H", "D", "T", "H", "H", "H", "DH", "DH", "A", "H", "H", "H", 
"DH", "D", "T", "H", "H", "H", "DH", "H"), .Dim = c(6L, 9L))

从右下角开始，目标是遵循方向（D = 对角移动到 0，H = 向左移动，V = 向上方移动），以便所有路径都到达零。正如您所看到的，有一些单元具有多个方向（例如DH）。

我试图通过这样的矩阵找到所有可能的路径。我用递归做到了。但我在正确存储路径方面遇到困难。似乎当函数返回到旧单元格以采取另一个方向时，它将路径附加到错误的列表中。

这是我的递归函数代码：

threading = function(matrix,i,j,list) { #Function wants the matrix to be threaded, number of rows and cols, and an empty list
  if (matrix[i,j] == 0) { #If the recursion has arrived at zero, stop and print out the path that arrived there
    print(list)
  }
  else { #If still elsewhere inside the matrix...
    for (move in strsplit(matrix[i,j],"")[[1]]) { #Iterate through each move in that cell
      if (move == "D") { #If a move is D...
        list = paste(list, "D", sep="") #Append that to the path
        threading(matrix,i-1,j-1,list) #Send the function to the diagonal cell
      }
      if (move == "V") { #If a move is V...
        list = paste(list, "V", sep="") #Append that to the path
        threading(matrix,i-1,j,list) #Send the function to the above cell
      }
      if (move == "H") { #If a move is H...
        list = paste(list, "H", sep="") #Append that to the path
        threading(matrix,i,j-1,list) #Send the function to the left cell
      }
    }
  }
}

因此，当我使用上面的矩阵运行它时，它会给出以下输出：

> threading(matrix, 6,9, emptylist)
[1] "HDDDDHH"
[1] "HDDDDHHD"
[1] "HDDHHDDD"

更关键的是，后两条路径的第二个字符是错误的，但其他一切都是正确的。我该如何避免这种情况？我不知道如何正确存储路径而不返回到旧路径。我认为这与附加的顺序和将函数发送到下一个单元格有关，但如果我反转它们，那么附加永远不会发生......

问题在于：

list = paste(list, "*", sep="")

当您点击有两个选择的单元格时，例如“VH”，for循环将经历两次迭代：list由第一次迭代修改，然后将该修改值传递给第二次迭代。相反，每次迭代都必须使用原始值。所以你可以替换为：

l = paste(list, "*", sep="")

并通过l代替list to the threading call.

另外，避免命名变量是一个很好的做法matrix or list因为它们也是函数的名称。