优化递归路径查找算法

Question

在输入上，我将获得矩阵的宽度和高度，文本字符串以及我要达到的另一个最终文本字符串。 第一个字符串的字符分配给矩阵。 我的目标是找到最短的方法来从矩阵中的字符中创建最终文本，从位置（0,0）开始，然后返回步骤数。

因此，我从FinalText创建了所有坐标和字符的字典。

Dictionary<Tuple<int, int>, char> coords = new Dictionary<Tuple<int, int>, char>();
for (int i = 0; i < height; i++)
{
  for (int j = 0; j < width; j++){
   if (finalText.Contains(matrix[j, i]))
    coords.Add(new Tuple<int, int>(j, i), matrix[j, i]);
  }
}

然后在我的功能中使用它。 我基本上在所有可能的路径中计算步骤，然后返回最短的步骤。

static int ShortestPath(char[,] matrix, string str, int x, int y, int steps, Dictionary<Tuple<int,int>,char> coords)
{
    if (str.Length == 0)
    {
        return steps;
    }

    else
    {
        List<int> l = new List<int>();

        foreach (var item in coords)
        {
            if (item.Value == str[0])
                l.Add(ShortestPath(matrix, str.Substring(1), item.Key.Item1, item.Key.Item2,
                    steps + (Math.Abs(x - item.Key.Item1) + Math.Abs(y - item.Key.Item2)), coords));
        }
                
        int min = l[0];
        for (int i = 1; i < l.Count; i++)
        {
            if (l[i] < min)
                min = l[i];
        }
        return min;
    }
}

该算法正在起作用，但是对于更大的矩阵来说，它太慢了，我不知道如何优化或进行否则。