Подсчет итогов Пути от (0,0) до (n-1, n-1) в сетке n * n

Question

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

Int path(int a[][200],int n,int m,int r,int c) 
    { 
     if(n == r - 1 && m == c-1) { 
      return 1; 
     } 
     else if(n >= r || m >= c || n < 0 || m < 0) { 
      return 0; 
     } 
     else if(vis[n][m] == 1) { 
      return 0; 
     } 
     else { 
      vis[n][m] = 1; 
      int x = path(a,n+1,m,r,c); 
      int y = path(a,n,m+1,r,c); 
      int u = path(a,n-1,m,r,c); 
      int v = path(a,n,m-1,r,c); 
      vis[n][m] = 0; 
      return (x+y+u+v); 
     } 
} 

Answer 1

Чтобы найти путь или сосчитать пути не совсем то же самое. Я предполагаю, что вы хотите просто посчитать пути (потому что заголовок вашего вопроса), и что вы можете только двигаться направо или двигаться вниз.

Для этого вам не нужна матрица (представляющая сетку) в качестве параметра. Ниже приведен простой (хотя и не эффективен) рекурсивное решение, которое также будет работать на * м сетки:

int countPaths(int m, int n) { 
    if (m == 0 || n == 0) 
     return 1; 

    return countPaths(m-1, n) + countPaths(m, n-1); 
} 

математическое решение для общего п * п сетка:

(2n choose n) = (2*n)!/(n!*n!)

Затем, сравнивая результаты с формулой:

countPaths(1, 1) == 2 // (2*1)!/(1!*1!)=2 

countPaths(2, 2) == 6 // (2*2)!/(2!*2!)=6 

countPaths(3, 3) == 20 // (2*3)!/(3!*3!)=20 

Ваш возвратами подход даст те же результаты, но с некоторыми соображениями. Например, рассмотрим, когда n=2, вы будете нуждаться в матрицу 3х3 (и вообще (n+1)x(n+1) матрица) для представления/изучения (и маркировать с 1) все пути для 2х2 сетки:

int countPaths(int a[][3],int n, int m, int r, int c) { 
     if(n == r-1 && m == c-1) { 
      return 1; 
     } 
     else if(n >= r || m >= c || n < 0 || m < 0) { 
      return 0; 
     } 
     else if(vis[n][m] == 1) { 
      return 0; 
     } 
     else { 
      vis[n][m] = 1; 
      int x = countPaths(a,n+1,m,r,c); 
      int y = countPaths(a,n,m+1,r,c); 
      vis[n][m] = 0; 
      return (x+y); 
     } 
} 

Тогда:

countPaths(vis, 0, 0, 3, 3) == 6 // (2*2)!/(2!*2!)=6