Modified rat in a maze

Question

It was asked me in an interview.you have given a m*n matrix filled with "1" and "0"."1" means you can use the cell and "0" means the cell is blocked.you can move in 4 directions left, right, top, bottom.every time you move upward direction or downward it cost you 1$.moving left or right will not be added to cost.so you have to write a code to check whether one can reach to destination index (x,y) starting from (0,0). If yes then print the minimum cost if no then print "-1".

I am not able to calculate the cost. Here is my code

public class Test {

    /**
     * @param args the command line arguments
     */
    static int dest_x = 0;
    static int dest_y = 0;
    static int cost = 0;
    static int m = 0;
    static int n = 0;

    public static void main(String[] args) {
        // TODO code application logic here
        Scanner in = new Scanner(System.in);
        Test rat = new Test();
        int maze[][] = {
                {1, 1, 1, 1},
                {1, 1, 1, 0},
                {1, 1, 1, 1},
                {0, 0, 1, 1}
        };
        dest_x = in.nextInt();
        dest_y = in.nextInt();
        m = in.nextInt();
        n = in.nextInt();
        if (rat.solveMaze(maze))
            System.out.println("YES");

        else {
            System.out.println("NO");
        }
        System.out.println("cost = " + cost);
    }

    boolean isSafe(int maze[][], int x, int y) {
        // if (x,y outside maze) return false
        return (x >= 0 && x < m && y >= 0 &&
                y < n && maze[x][y] == 1);
    }

    boolean solveMaze(int maze[][]) {
        int sol[][] = {{0, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 0, 0},
                {0, 0, 0, 0}
        };

        if (!solveMazeUtil(maze, 0, 0, sol)) {
            return false;
        }
        return true;
    }

    boolean solveMazeUtil(int maze[][], int x, int y, int sol[][]) {
        // if (x,y is goal) return true
        if (x <= dest_x || y <= dest_y)
            if (x == dest_x && y == dest_y) {
                sol[x][y] = 1;
                return true;
            } else if (sol[x][y] == 1) {
                return false;
            }

            // Check if maze[x][y] is valid
            else if (isSafe(maze, x, y)) {
                // mark x,y as part of solution path
                sol[x][y] = 1;

                // Move forward in x direction 
                if (solveMazeUtil(maze, x + 1, y, sol)) {
                    //System.out.println("here at x+1 x = " + x  + " y = " + y);
                    return true;
                }

                // Move down in y direction 
                if (solveMazeUtil(maze, x, y + 1, sol)) {
                    //System.out.println("here at y+1 x = " + x  + " y = " + y);
                    cost++;
                    return true;
                }
                cost--;
                if (solveMazeUtil(maze, x - 1, y, sol)) {
                    // System.out.println("here at x-1 x = " + x  + " y = " + y);  
                    return true;
                }
                if (solveMazeUtil(maze, x, y - 1, sol)) {
                    //System.out.println("here at y-1 x = " + x  + " y = " + y);  
                    cost++;
                    return true;
                }
                cost--;
                /* If no solution then
                   BACKTRACK: unmark x,y as part of solution
                   path */
                sol[x][y] = 0;
                return false;
            }
        return false;
    }
}

Answer 1

Turn the maze into a Directed Graph and solve shortest path problem

1. Cells which are marked by "1" are nodes (marked by "0" should be ignored)
2. If we can move from one cell (node) to another, connect them with a directed edge; put cost (0 or 1) on the edge (please, notice, that we have a multigraph: two nodes can be connected with two different edges).
3. Finally, with a help of Dijkstra's algorithm find the shortest path (i.e. min cost) between required nodes.