Solution in java for : Finding if a path exists from start to end cell in a maze | Back Tracking and Dynamic Programming

Hello Friends,

Today I am here with you with a recursion problem. Today we have a little tough problem.

Suppose we have a maze and we need to determine if a path exits from starting point  to the last point in the maze. Maze is represented by a 2-d-matrix. Lets call this matrix 'maze'. maze[0][0] represents the starting point and maze[rows-1][columns-1] be the end point. Any cell 'maze[i][j]' can be used as a part of the path if it contains 1 and can be reached from immediate top, left, right or bottom cells. Cells containing 0 are the ones which can not be used in the path.

Friends I have tried solving this using two Approaches.
    1. Recursion [Back Tracking] : Depth search First approach : DFS
    2. Dynamic Programming.

**Note that Dynamic programming approach will fail for few examples where path exists by traversing upwards or left side like below example

1 1 1 1 0 0 0 0
0 0 0 1 0 1 1 1
0 1 1 1 0 1 0 1
0 1 0 0 0 1 0 1
0 1 1 1 1 1 0 1


Friends please find below the code for this problem.

package com.recursion.backtracking;

public class Maze {
    public static void main(String[] args) {
        int mazeForDFS[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        int mazeForDP[][] = { 
                { 1, 1, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 1, 1, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 },
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 0, 0, 0, 0 }, 
                { 0, 0, 1, 1, 1, 1, 0 }, 
                { 0, 0, 1, 1, 0, 1, 0 },
                { 1, 1, 0, 0, 0, 1, 1 } 
                
        };
        
        boolean isPathAvailableDFS = isPathAvailable(mazeForDFS, 0, 0, mazeForDFS.length, mazeForDFS[0].length);
        boolean isPathAvailableDP = isPathAvailable(mazeForDP);
        System.out.println("DFS way : " + isPathAvailableDFS);
        System.out.println("DP  way : " + isPathAvailableDP);
    }

    public static final int VISITED = 0;

    /**
     * This is a recursive approach based upon recursion and Back tracking. If a
     * end point is reached then true is returned all the way up to the first
     * calling of the method, else false is returned. False is propagated  down
     * the call stack if all the options [top, left, right, down] are explored
     * and no other cell is left to explore.
     * 
     * @param maze
     * @param i
     * @param j
     * @param rows
     * @param columns
     * @return true if path exists else returns false;
     */
    public static boolean isPathAvailable(int[][] maze, int i, int j, int rows, int columns) {
        if (i == rows - 1 && j == columns - 1) {
            return true;
        }
        maze[i][j] = VISITED;
        if (j + 1 < columns && maze[i][j + 1] != VISITED) {
            if (isPathAvailable(maze, i, j + 1, rows, columns)) {
                return true;
            }
        }
        if (i + 1 < rows && maze[i + 1][j] != VISITED) {
            if (isPathAvailable(maze, i + 1, j, rows, columns)) {
                return true;
            }
        }
        if (j - 1 >= 0 && maze[i][j - 1] != VISITED) {
            if (isPathAvailable(maze, i, j - 1, rows, columns)) {
                return true;
            }
        }
        if (i - 1 >= 0 && maze[i - 1][j] != VISITED) {
            if (isPathAvailable(maze, i - 1, j, rows, columns)) {
                return true;
            }
        }
        return false;
    }

    /**
     * This method uses Dynamic programming to solve the problem. It exploits
     * the information for all the first row and column information and then
     * verifies the rest of the cells if they are reachable. In case they are
     * not reachable this method marks them as 0, as they are as good as cells
     * with value = 0;
     * 
     */
    public static boolean isPathAvailable(int[][] maze) {
        int rows = maze.length;
        int coloumns = maze[0].length;
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < coloumns; j++) {
                if (maze[i][j] == 1 && maze[i - 1][j] == 0 && maze[i][j - 1] == 0) {
                    maze[i][j] = 0;
                }
            }
        }
        return maze[rows - 1][coloumns - 1] == 1;
    }
}