CODEWITHSUNDEEP
algorithmrecursiondynamic-programminggraph-algorithmmaze
tubby
tubby

Reputation: 2144

count paths from source to destination in a matrix moving in all 4 directions

Say, I have a matrix of size n*n and I want to traverse from 0,0 to n-1,n-1 if I'm allowed to move in all four directions - right,left,up and down. How do I find all paths using recursion.

Below is my approach for doing this given you're allowed to move in only 2 directions - right and 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;
    }

However, when allowed to move in all four directions, this does not work, if I were to add the additional recursive steps to the left and up. This is due to the fact that cycles are generated, as in going from 0,1 to 0,0 and then back to 0,0 leading to an infinite loop. I have tried to avoid this by maintaining a visited two-dimensional array, and returning 0 if already visited. However, I don't think that gives me the correct output since the problem is to count paths, and not just do a traversal.

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

How can I count all paths from source to destination in a matrix moving in all 4 directions

Upvotes: 3

Views: 3497

Answers (2)

Chimo Jiang
Chimo Jiang

Reputation: 1

Agree with the dfs algorithm, however the base case check need add visited[i][j] to check the duplicated visit.

if (i < 0 || i >= n || j < 0 || j >= n || visited[i][j]) {
            return 0;
}

Upvotes: 0

Juan Lopes
Juan Lopes

Reputation: 10565

Try setting visited[i][j] = false when exiting a cell. But beware: this is not a dynamic programming solution (I'm convinced that there is no DP solution to this problem). Instead, you're doing an unbounded search (a kind of backtracking):

Also: fixed the bug if (visited[i][i]) ... in your code.

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

Upvotes: 3

Related Questions