Recursive headache

Question

The task:

Given a 2D array m containing whole non negative numbers, we will define a "path" as a collection of neighboring cells(diagonal steps do not count as neighbor) starting at 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 of the possible paths in an array:

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

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

TO DO:

Write a static recursive method that accepts a 2D array m filled with whole non negative values and prints the sum of all the possible path costs(you may assume that m is not null nor empty).

Method signature is(overloading is allowed):

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

My code:

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

    }

}

The printed value of the above code is: 14

Which is less than expected!

When ran with:

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

The result is 6 as expected.

What is wrong in my code?

PS: please do not present me with code that solves the assignment but explain what is wrong with my code.

Answer 1

As Paul said, the change your code needs is to revert the set of visited cells after the recursive calls. It 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 2

The code marks cells visited as soon as an arbitrary path reaches that cell. But this cell is afterwards aswell marked as visited for all other cells and won't be visited again. This means the algorithm only finishes a subset of the paths and some traversals break off somewhere in the middle of the array for bigger arrays. You'll have to mark the cells as visited separately for each path.

Simply reset the map after each access of a new cell:

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

        int tmp = visitAllNeighbours()

        resetVisitedState(currentCell)

        return tmp

This would be the most efficient and simple way. Since the cellstate is reset after accessing the cell, it will never remain marked from the previous path.

Answer 3

As I see it you are calculating the sum of the weights of all the cells at a time in only one recursion. But not considering the fact that the paths may intersect and that any two paths can have cells in common.like the two paths shown in the illustration have cells in common and have to be added twice