4. 最小路徑程式

List<List<int>> arr = new List<List<int>>();
Console.Write("請輸入一個二維陣列: ");
var str = Console.ReadLine();
for (int i = 1; i < str.Length - 1; i++)
{
    if (str[i] == '[')
    {
        var list = new List<int>();
        var end = str.IndexOf(']', i);
        var data = str.Substring(i + 1, end - i - 1);
        var v = data.Split(',');
        for (global::System.Int32 j = 0; j < v.Length; j++)
            list.Add(int.Parse(v[j]));

        i = end + 1;
        arr.Add(list);
    }
}

Console.WriteLine("數字地圖:");
for (int i = 0; i < arr.Count; i++)
{
    var k = arr[i];
    Console.Write("\t[");
    for (int j = 0; j < k.Count; j++)
    {
        Console.Write(k[j]);
        if (j != k.Count - 1) Console.Write(", ");
    }
    Console.WriteLine("]");
}

List<List<int>> paths = new List<List<int>>();
void run(int x, int y, List<int> current)
{
    if (y == arr.Count - 1 && x == arr[0].Count - 1)
    {
        current.Add(arr[arr.Count - 1][arr[0].Count - 1]);
        paths.Add(current);
        return;
    }
    var a = new List<int>(current);
    a.Add(arr[y][x]);

    if (y + 1 != arr.Count)
        run(x, y + 1, new List<int>(a));
    if (x + 1 != arr[0].Count)
        run(x + 1, y, a);
}
run(0, 0, new List<int>());

if (arr[0].Count + arr.Count < 8)
{
    Console.WriteLine("所有路徑:");
    foreach (var a in paths)
    {
        Console.WriteLine($"\t[{string.Join(", ", a)}]");
    }
}

int minLen = int.MaxValue;
List<int> path = null;
foreach (var item in paths)
{
    var sum = 0;
    foreach (var item1 in item)
    {
        sum += item1;
    }
    if (sum < minLen) minLen = sum;
    path = item;
}

Console.WriteLine($"最小路徑:  [{string.Join(", ", path)}]");
Console.WriteLine($"最小路徑和:  {minLen}");