счета пути от источника к месту назначения в матрице, движущиеся во всех 4-х направлениях

Question

Сай, у меня есть матрица размера n*n, и я хочу, чтобы пройти от 0,0 к n-1,n-1, если мне позволено двигаться во всех четырех направлениях - right, left , up и down. Как найти все пути, используя рекурсию.

Ниже приведен мой подход для этого, поскольку вам разрешено перемещаться только в двух направлениях - right и down.

static int findWays2directions(int[][] a, int i, int j) { 
     if (i < 0 || j < 0 || i == a.length || j == a[0].length) 
      return 0; 

     if (i == a.length - 1 && j == a[0].length - 1) 
      return 1; 

     int right = findWays2directions(a, i, j + 1); 
     int down = findWays2directions(a, i + 1, j); 
     return right + down; 
    } 

Однако, когда разрешено двигаться во всех четырех направлениях, это не сработает, если бы я, чтобы добавить дополнительные рекурсивные шаги к left и up. Это связано с тем, что генерируются циклы, как при переходе от 0,1 в 0,0, а затем обратно в 0,0, приводящем к бесконечному циклу. Я пытался избежать этого, поддерживая двумерный массив visited и возвращая 0, если он уже был посещен. Тем не менее, я не думаю, что это дает мне правильный результат, поскольку проблема заключается в подсчете путей, а не просто обход.

static int findWays4directions(int[][] a, int i, int j, boolean[][] visited) { 
     if (i < 0 || j < 0 || i == a.length || j == a[0].length) 
      return 0; 

     if (i == a.length - 1 && j == a[0].length - 1) 
      return 1; 

     if (visited[i][i] == true) 
      return 0; 

     visited[i][j] = true; 

     int right = findWays4directions(a, i, j + 1, visited); 
     int down = findWays4directions(a, i + 1, j, visited); 
     int left = findWays4directions(a, i, j - 1, visited); 
     int up = findWays4directions(a, i - 1, j, visited); 

     return left + down + right + up; 
    } 

Как я могу рассчитывать все пути от источника к месту назначения в матрице перемещения во всех 4-х направлениях

Answer 1

Попробуйте установить visited[i][j] = false при выходе из ячейки. Но будьте осторожны: это не динамическое программирующее решение (я убежден, что для решения этой проблемы не существует DP). Вместо этого вы выполняете неограниченный поиск (вид обратного отслеживания):

Также: исправлена ​​ошибка if (visited[i][i]) ... в вашем коде.

static int findWays4directions(int[][] a, int i, int j, boolean[][] visited) { 
    if (i < 0 || j < 0 || i == a.length || j == a[0].length) 
     return 0; 

    if (i == a.length - 1 && j == a[0].length - 1) 
     return 1; 

    if (visited[i][j] == true) 
     return 0; 

    visited[i][j] = true; 

    int right = findWays4directions(a, i, j + 1, visited); 
    int down = findWays4directions(a, i + 1, j, visited); 
    int left = findWays4directions(a, i, j - 1, visited); 
    int up = findWays4directions(a, i - 1, j, visited); 

    visited[i][j] = false; 

    return left + down + right + up; 
}