Обход матрицы всеми путями

Question

Нужен алгоритм обхода матрицы всеми путями от начала и до конца. Пример как обходить, есть на фото. При этом, это пример для 3 строк и 3 столбцов, а нужно, чтобы хотя бы строки можно было задавать.

Answer 1

Для вывода всех путей проще всего использовать рекурсивную функцию.

function walk(X,Y, path)
   Если достигнута последняя ячейка - вывести путь. return
   Если не достигнута последняя строка, вызвать walk c тем же X, с Y+1, добавить в текущий путь пару X,Y
   Если не достигнут последний столбец, вызвать walk c X+1, Y, добавить в текущий путь пару X,Y

namespace ConsoleApp5
{
    class Program
    {
        static void walk(int x, int y, int rows, int cols, string s)
        {
            if (x == cols - 1 & y == rows - 1)
            {
                Console.WriteLine(s);
                return;
            }
            if (x < cols - 1)
                walk(x + 1, y, rows, cols, s + String.Format(" ({0},{1})", y, x));
            if (y < rows - 1)
                walk(x, y + 1, rows, cols, s + String.Format(" ({0},{1})", y, x));

        }

        static void Main(string[] args)
        {
            int cols = 3;
            int rows = 3;
            walk(0, 0, rows, cols, "");
            Console.ReadKey();
        }
    }
}

Если пути нужно просто подсчитать, понадобится формула для числа сочетаний C(n+m, m)

Answer 2

В комментах выяснилось, что реальная задача несколько в другом (как говорится, a kind of XY problem).

Задачу нахождения наиболее выгодного пути можно решать с помощью динамического программирования.

Создаём матрицу такого же размера. Обходим ячейки построчно. Для каждой ячейки выбираем, приходит ли наиболее выгодный путь в неё слева или сверху, и записываем в неё минимум из тех двух плюс собственный вес.

 B[i][j] = A[i][j] + min(B[i-1][j], B[i][j-1])

Первую строку и первый столбец можно обработать особым образом.

БЛОГ НА HUSL

Обход матрицы всеми путями

Ответы (2 шт):