Recursive headache

Question

Challenge :

Given a 2D array m containing non-negative integers , we define a “path” as a set of neighboring cells ( do diagonal steps not be considered a neighbor ) starting from row == 0 && col == 0 and ending with row == m.length - 1 && col == m[0].length - 1 .

the cost of a "path" is the sum of the values ​​in each cell of the "path".

Example:

Two possible paths in an array:

The cost of path 1 (dashed line): 8 + 4 + 2 + 8 + 9 + 9 + 7 + 5 = 52;

Cost of path 2 (full line): 8 + 6 + 3 + 8 + 9 + 4 + 1 + 2 + 1 + 7 + 6 + 5 = 60

MAKE:

Write a recursive static method that takes a 2D array m filled with non-negative integer values and prints the sum of all possible costs on the path (you can assume that m not null and not empty).

Method signature (overload allowed):

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

My code is:

 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]); } } 

Print value of above code: 14

This is less than expected!

When starting with:

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

The result is 6.

What is wrong in my code?

PS: please do not tell me the code that decides the purpose, but explain what is wrong with my code.

Answer 1

Cells of code are marked as soon as an arbitrary path reaches this cell. But this cell is subsequently also marked as visited for all other cells and will no longer be visited. This means that the algorithm is only completing a subset of the paths, and some traversals are interrupted somewhere in the middle of the array for large arrays. You will need to mark the cells as visited separately for each path.

Just reset the card after each access to the new cell:

  printPathWeights(...) //analyze the current cell markCellVisited(currentCell) int tmp = visitAllNeighbours() resetVisitedState(currentCell) return tmp 

This will be the most efficient and easiest way. Since cellState reset after accessing the cell, it will never remain marked from the previous path.

Answer 2

As Paul said, changing the needs of your code is to return a set of visited cells after recursive calls. He prints 76 , as expected.

 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; } } 

Answer 3

As I see it, you calculate the sum of the weights of all cells at a time in just one recursion. But not taking into account the fact that the paths can intersect and that any two paths can have common cells. Just as the two paths shown in the illustration share cells and must be added twice