Как найти все возможные пути от (1, 1) до (m, n) в матрице m × n?

Question

Предположим, у нас есть матрица m × n с начальным индексом (1, 1). Мы должны достичь положения (m, n), двигаясь вправо или вниз к соседнему элементу. Как мы можем исследовать все возможные пути?

Answer 1

Поворот * Треугольник Pascal 1/8 оборота:

1  1  1  1  1 ...
1  2  3  4  5 ...
1  3  6 10 15 ...
1  4 10 20 35 ...

Элемент [M, N] этой матрицы - ваш желаемый ответ.

Конструкция этого массива Изоморфность c к треугольнику Pascal:

Начало в (1, 1); Есть только один способ добраться до этого места. Следующий ход - либо (2, 1), либо (1, 2) - только один способ добраться до этой точки. На следующем ходу теперь есть два способа достижения (2, 2): это достижимо из любого из предыдущих мест, поэтому число путей составляет сумма из этих двух элементы. Это критический изоморфизм с треугольником Pascal.

---

Точнее, просто используйте формулу для любого элемента треугольника:

(a+b)! / a!b!

Где a = M-1 , b = N-1

Это количество необходимых вам ходов right и down с использованием формулы комбинатори c для всех его перестановок.

Answer 2

Чтобы достичь (N, M) из (1, 1), необходимо go (N-1) шаг вправо и (M-1) шаг вниз.

Вы можете обозначьте путь, перечислив движения «вправо» (r) и «вниз» (d), например, rddrd для вправо, вниз, вниз, вправо вниз.

Теперь, поскольку у вас есть до go (N-1) r -шагов и (M-1) d -шагов, у вас есть (N-1) + (M-1) шагов. В математике это означает, что вы хотите сгенерировать все «d-r -последовательности с (N-1) + (M-1) символами, где точно (N-1) равно r». Это подробно описано здесь .

Answer 3

Это может быть сделано рекурсивно ,

. При заданной позиции (x, y) у нас есть two выбор - right или down.

Мы можем выбрать any и проверим нашу цель (m, n). Если в любое время x exceeds m (или y exceeds n) STOP.

Во время обхода мы можем сохранить путь к некоторому list/array (в зависимости от вашей реализации).

Pseudo код:

   waysToReach(startX, startY, endX, endY, path)
   {
      if (startX > endX || startY > endY)
         return;

      if (startX == endX && startY == endY)
      {
         count++;
         println(count+ ". " + path);
         return;
      }

      // Right traverse
      add 1 to path; // 1 for right
      waysToReach(startX + 1, startY, endX, endY, path);

      remove last-step from path;

      // Down traverse
      add 0 to path; // 0 for down
      waysToReach(startX + 1, startY, endX, endY, path);

      remove last-step from path;
   }

Я реализовал свою идею в Java, если вам нужен код, я могу предоставить вам,

Для примера , когда m=3 и n=4, существует в общей сложности 10 способов, они следующие: здесь 1 для ПРАВО , 0 для ВНИЗ .

1. [1, 1, 0, 0, 0]
2. [1, 0, 1, 0, 0]
3. [1, 0, 0, 1, 0]
4. [1, 0, 0, 0, 1]
5. [0, 1, 1, 0, 0]
6. [0, 1, 0, 1, 0]
7. [0, 1, 0, 0, 1]
8. [0, 0, 1, 1, 0]
9. [0, 0, 1, 0, 1]
10. [0, 0, 0, 1, 1]

когда m=6 и n=3, существует в общей сложности 10 способов, это следующие: здесь 1 для ПРАВО , 0 для ВНИЗ .

1. [1, 1, 1, 1, 1, 0, 0]
2. [1, 1, 1, 1, 0, 1, 0]
3. [1, 1, 1, 1, 0, 0, 1]
4. [1, 1, 1, 0, 1, 1, 0]
5. [1, 1, 1, 0, 1, 0, 1]
6. [1, 1, 1, 0, 0, 1, 1]
7. [1, 1, 0, 1, 1, 1, 0]
8. [1, 1, 0, 1, 1, 0, 1]
9. [1, 1, 0, 1, 0, 1, 1]
10. [1, 1, 0, 0, 1, 1, 1]
11. [1, 0, 1, 1, 1, 1, 0]
12. [1, 0, 1, 1, 1, 0, 1]
13. [1, 0, 1, 1, 0, 1, 1]
14. [1, 0, 1, 0, 1, 1, 1]
15. [1, 0, 0, 1, 1, 1, 1]
16. [0, 1, 1, 1, 1, 1, 0]
17. [0, 1, 1, 1, 1, 0, 1]
18. [0, 1, 1, 1, 0, 1, 1]
19. [0, 1, 1, 0, 1, 1, 1]
20. [0, 1, 0, 1, 1, 1, 1]
21. [0, 0, 1, 1, 1, 1, 1]