Рекурсивная головная боль

Question

Задача:

Учитывая 2D массив m, содержащего целого неотрицательного числа, мы определим «пути» как совокупность соседних ячеек (диагональные шаги не считаются сосед), начиная с row == 0 && col == 0 и заканчивая row == m.length - 1 && col == m[0].length - 1.

стоимость «путь» - это сумма значений в каждой ячейке «пути».

Пример:

Два из возможных путей в массиве:

Стоимость пути 1 (пунктирная линия): 8 + 4 + 2 + 8 + 9 + 9 + 7 + 5 = 52;

Стоимость пути 2 (полная линия): 8 + 6 + 3 + 8 + 9 + 4 + 1 + 2 + 1 + 7 + 6 + 5 = 60

сделать:

Написать static рекурсивного метод, который принимает массив 2D m заполненного целых неотрицательных значений и печатает сумму всех возможных затрат на пути (вы можете считать, что m не null или пустые).

Метод подписи (перегрузка допускается):

public static void printPathWeights(int [][] m)

Мой код:

public class Main { 

    public static void main(String[] args) { 

     int arr[][] = { { 1, 1, 1 }, 
         { 1, 1, 1 }, 
         { 1, 1, 1 } 
     }; 

     printPathWeights(arr); 

    } 

    public static void printPathWeights(int[][] m) { 
     System.out.println(printPathWeights(m, 0, 0, new int[m.length][m[0].length], 0)); 
    } 


    /* 
    * @param map marks the visited cells 
    */ 
    private static int printPathWeights(int[][] m, int row, int col, int[][] map, int carrier) { 

     if (row < 0 || col < 0 || row >= m.length || col >= m[0].length || map[row][col] == 1) 
      return 0; 

     if (row == m.length - 1 && col == m[0].length - 1) 
      return m[row][col] + carrier; 

     map[row][col] = 1; 
     return printPathWeights(m, row + 1, col, map, carrier + m[row][col]) + 
       printPathWeights(m, row - 1, col, map, carrier + m[row][col]) + 
       printPathWeights(m, row, col + 1, map, carrier + m[row][col]) + 
       printPathWeights(m, row, col - 1, map, carrier + m[row][col]); 

    } 

} 

Напечатанный значение выше код: 14

Что меньше, чем ожидалось!

Когда бежал с:

int arr[][] = { { 1, 1 }, 
        { 1, 1 } 
    }; 

В результате получается 6, как и ожидалось.

Что не так в моем коде?

PS: пожалуйста, не сообщайте мне код, который решает задачу, но объясните, что не так с моим кодом.

Answer 1

Коды маркируют ячейки, которые посещают, как только произвольный путь достигает этой ячейки. Но эта ячейка впоследствии также отмечена как посещенная для всех других ячеек и больше не будет посещаться. Это означает, что алгоритм только заканчивает подмножество путей, а некоторые обходы прерываются где-то посередине массива для больших массивов. Вам нужно будет пометить ячейки как посещенные отдельно для каждого пути.

Просто сбросить карты после каждого доступа к новой ячейки:

printPathWeights(...) 
     //analyze the current cell 
     markCellVisited(currentCell) 

     int tmp = visitAllNeighbours() 

     resetVisitedState(currentCell) 

     return tmp 

Это было бы наиболее эффективным и простым способом. Поскольку cellState сбрасывается после доступа к ячейке, он никогда не останется отмеченным от предыдущего пути.

Answer 2

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

Answer 3

Как сказал Павел, измените свой потребность в коде состоит в том, чтобы вернуть набор посещенных ячеек после рекурсивных вызовов. Он печатает 76, как и ожидалось.

public class Main { 

    public static void main(String[] args) { 

     int arr[][] = { { 1, 1, 1 }, 
         { 1, 1, 1 }, 
         { 1, 1, 1 } 
     }; 

     printPathWeights(arr); 

    } 

    public static void printPathWeights(int[][] m) { 
     System.out.println(printPathWeights(m, 0, 0, new int[m.length][m[0].length], 0)); 
    } 

    /* 
    * @param map marks the visited cells 
    */ 
    private static int printPathWeights(int[][] m, int row, int col, int[][] map, int carrier) { 

     if (row < 0 || col < 0 || row >= m.length || col >= m[0].length || map[row][col] == 1) 
      return 0; 

     if (row == m.length - 1 && col == m[0].length - 1) 
      return m[row][col] + carrier; 

     map[row][col] = 1; 
     int result = printPathWeights(m, row + 1, col, map, carrier + m[row][col]) + 
       printPathWeights(m, row - 1, col, map, carrier + m[row][col]) + 
       printPathWeights(m, row, col + 1, map, carrier + m[row][col]) + 
       printPathWeights(m, row, col - 1, map, carrier + m[row][col]); 
     map[row][col] = 0; // Here 
     return result; 
    } 
}