Рекурсия с 2-мерным массивом

Question

Я пишу рекурсивный метод, чтобы найти все возможные пути в двумерном массиве. От верхней левой точки (0,0) до нижней правой точки последней точки. И возвращает суммы путей.

public static void printPathWeights(int[][] m) 
{ 
    printPathWeights(m, 0, 0, 0); 
} 

public static void printPathWeights(int[][] m, int row, int col, int sum) 
{ 
    if(row == 0 && col ==0) 
    sum = 0; 

    if (row == m.length - 1 && col == m[row].length - 1) 
     System.out.println(sum); 

    else 
    { 
     if (row >= 0 && row < m.length && col >= 0 && col < m[row].length) 
     printPathWeights(m, row - 1, col, sum += m[row][col]); // Up 
     if (row >= 0 && row < m.length && col >= 0 && col < m[row].length) 
      printPathWeights(m, row + 1, col, sum += m[row][col]); // Down 
     if (row >= 0 && row < m.length && col >= 0 && col < m[row].length) 
      printPathWeights(m, row, col - 1, sum += m[row][col]); // Left 
     if (row >= 0 && row < m.length && col >= 0 && col < m[row].length) 
      printPathWeights(m, row, col + 1, sum += m[row][col]); // Right 
    } 
} 

В настоящее время моя проблема заключается в том, что эта функция попасть в бесконечный цикл и не печатать мою сумму

Answer 1

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

Answer 2

Я думаю, что это застрять на:

if (row >= 0 && row < m.length && col >= 0 && col < m[row].length) 
     printPathWeights(m, row, col - 1, sum += m[row][col]); // Left 
if (row >= 0 && row < m.length && col >= 0 && col < m[row].length) 
     printPathWeights(m, row, col + 1, sum += m[row][col]); // Right 

Он будет постоянно держать прыгает взад и вперед.

И, как указал Микель, почему пути не могут подняться?

Решение: (Предполагается, что пути не могут пересекаться друг с другом, в противном случае сумма уходит на бесконечность)

• Отслеживайте, где вы были. Передайте эту историю следующей рекурсии.

• Добавьте значение плитки, на которой вы находитесь, к суммарному значению, которое передавалось как параметр.

• Если вы на финише, распечатайте сумму.

• Else: Постарайтесь пойти в четырех возможных направлениях. Это не удастся, если в этом направлении нет ячейки, IE вы на краю. Он также потерпит неудачу, если вы уже были там.

• Если вы не можете двигаться никуда, IE вы застреваете, вы возвращаетесь, ничего не делая.

Answer 3

public static void printPathWeights(int [][] m) 
{ 
printPathWeights (m, 0, 0, 0); 
} 

private static void printPathWeights(int [][]m, int i, int j,int sum) 
{ 
if (i<0 || i>=m.length || j<0 || j>=m[0].length) 
return; 
if (m[i][j] == -1) 
return; 
if (i==m.length-1 && j==m[0].length-1) 
System.out.println (sum + m[m.length-1][m[0].length-1]); 
int temp = m[i][j]; 
m[i][j] = -1; 
printPathWeights (m, i+1, j, sum+temp); 
printPathWeights (m, i, j+1, sum+temp); 
printPathWeights (m, i-1, j, sum+temp); 
printPathWeights (m, i, j-1, sum+temp); 
m[i][j] = temp; 
    } 

попробовать это, вы положить -1 в месте, вы уже раньше, и сложите вы помещаете обратно номера, и готовы в течение следующих путей

Answer 4

Полный рабочий код , Испытано ...

государственной статической силы printPathWeights (ИНТ [] [] м) {

printPathWeights(m, 0, 0, 0, 0); 

}

// 1 - Если правая ячейка ясно, 2 - Если левая ячейка понятно, 0 - нейтральные

частные статические INT printPathWeights (INT [] [] м, INT сумма, Int флаг, Int строка, Int Col) {

if (row == m.length - 1 && col == m[0].length - 1){ 
     System.out.print((sum + m[row][col]) + " "); 
     return sum; 
    } 

    //Check if the RIGHT cell legal - (That's to say current cell was not called by the rigth cell 
    // and the boundry is legal) 
    if(flag != 1 && ((col+1) <= m[0].length - 1)) 
     printPathWeights(m, sum + m[row][col], 2, row, col + 1); 

    //Check if the DONN/Below cell is legal - (That is to say the boundry is legal. We do not check 
    // if we came from below cell since we do not have 'UP' call) 
    if(((row+1) <= m.length - 1)) 
     printPathWeights(m, sum + m[row][col], 0, row + 1, col); 

    //Check if the LEFT cell legal - (That's to say current cell was not called by the LEFT cell 
    // and the boundry is legal and if We are at the top level we DO NOT TURN LEFT) 
    if(flag != 2 && ((col - 1) >= 0) && row != m.length - 1) 
     printPathWeights(m, sum + m[row][col], 1, row, col - 1); 

    return sum; 

}