Google Foobar challenge: Exiting a space station maze, where one wall may be removed

Question

I'm solving Foobar challenge. My code runs perfectly in eclipse but when i verify it on foobar it says

Execution took too long .

The question is - You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).

Write a function answer(map) that generates the length of the shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.

Test cases

Inputs:(int) maze = [[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]]

Output: (int) 7

Inputs: (int) maze = [[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]] Output: (int) 11

My code :

class Maze{
    Maze(int i,int j){
        this.flag=false;
        this.distance=0;
        this.x=i;
        this.y=j;
    }
    boolean flag;
    int distance;
    int x;
    int y;
}

public class Answer{
    public static boolean isPresent(int x,int y,int r,int c)
    {
        if((x>=0&&x<r)&&(y>=0&&y<c))
            return true;
        else
            return false;
    }
    public static int solveMaze(int[][] m,int x,int y,int loop)
    {
        int r=m.length;
        int c=m[0].length;
        int result=r*c;
        int min=r*c;
        Maze[][] maze=new Maze[r][c];//Array of objects
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                maze[i][j]=new Maze(i,j);
            }
        }
        Queue<Maze> q=new LinkedList<Maze>();

        Maze start=maze[x][y];
        Maze[][] spare=new Maze[r][c];
        q.add(start);//Adding source to queue
        int i=start.x,j=start.y;
        while(!q.isEmpty())
        {
            Maze temp=q.remove();
            i=temp.x;j=temp.y;
            int d=temp.distance;//distance of a cell from source 
            if(i==r-1 &&j==c-1)
            {
                result=maze[i][j].distance+1;
                break;
            }
            maze[i][j].flag=true;
            if(isPresent(i+1,j,r,c)&&maze[i+1][j].flag!=true)//check down of current cell
            {
                if(m[i+1][j]==0)//if there is path, add it to queue
                {
                    maze[i+1][j].distance+=1+d;
                    q.add(maze[i+1][j]);
                    maze[i][j].flag=true;
                }
                if(m[i+1][j]==1 && maze[i+1][j].flag==false && loop==0)//if there is no path, see if breaking the wall gives a path.
                {
                    int test=solveMaze(m,i+1,j,1);
                    if(test>0)
                    {
                        test+=d+1;
                        min=(test<min)?test:min;
                    }
                    //  maze[i+1][j].flag=true;
                }
            }
            if(isPresent(i,j+1,r,c)&&maze[i][j+1].flag!=true)//check right of current cell
            {
                if(m[i][j+1]==0)
                {
                    maze[i][j+1].distance+=1+d;
                    q.add(maze[i][j+1]);
                }
                if(m[i][j+1]==1 && maze[i][j+1].flag==false && loop==0)
                {
                    int test=solveMaze(m,i,j+1,1);
                    if(test>0)
                    {
                        test+=d+1;
                        min=(test<min)?test:min;
                    }
                    maze[i][j+1].flag=true;
                }
            }
            if(isPresent(i-1,j,r,c)&&maze[i-1][j].flag!=true)//check up of current cell
            {
                if(m[i-1][j]==0)
                {
                    maze[i-1][j].distance+=1+d;
                    q.add(maze[i-1][j]);
                }
                if(m[i-1][j]==1 && maze[i-1][j].flag==false && loop==0)
                {
                    int test=solveMaze(m,i-1,j,1);
                    if(test>0)
                    {
                        test+=d+1;
                        min=(test<min)?test:min;
                    }
                    maze[i-1][j].flag=true;
                }
            }
            if(isPresent(i,j-1,r,c)&&maze[i][j-1].flag!=true)//check left of current cell
            {
                if(m[i][j-1]==0)
                {
                    maze[i][j-1].distance+=1+d;
                    q.add(maze[i][j-1]);
                }
                if(m[i][j-1]==1 && maze[i][j-1].flag==false && loop==0)
                {
                    int test=solveMaze(m,i,j-1,1);
                    if(test>0)
                    {
                        test+=d+1;
                        min=(test<min)?test:min;
                    }
                    maze[i][j-1].flag=true;
                }
            }
        }
        return ((result<min)?result:min);

    }
    public static int answer(int[][] m)
    {
        int count;
        int r=m.length;
        int c=m[0].length;
        count=solveMaze(m,0,0,0);
        return count;
    }
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        System.out.println("enter row size ");
        int m=sc.nextInt();
        System.out.println("enter column size ");
        int n=sc.nextInt();
        int[][] maze=new int[m][n];
        System.out.println("Please enter values for maze");
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                maze[i][j]=sc.nextInt();
            }
        }
        int d=answer(maze);
        System.out.println("The maze can be solved in "+d+" steps");
    }
}

Answer 1

It looks like your current implementation is wrong. Running it on a simple 2x2 square without walls should give 2 steps (move right, move down). But your program answers with 4.

Because it's wrong, we're not supposed to even answer this question, but let me give you some tips to get started anyway (without actually fixing your problem, that's still your own job).

Test without manual input

Instead of inputting the numbers each time, it's easier to test if you have some mazes hard coded. This can be easily achieved like this:

    public static void main(String[] args) {
        int[][] maze = new int[][]{
                {0, 0},
                {0, 0}};
//        int[][] maze = new int[][]{
//                {0, 1, 1, 0}, 
//                {0, 0, 0, 1},
//                {1, 1, 0, 0}, 
//                {1, 1, 1, 0}};
//        int[][] maze = new int[][]{
//                {0,1,0},
//                {1,0,0},
//                {0,0,0}};
        int d = answer(maze);
        System.out.println("The maze can be solved in " + d + " steps");
    }

You can comment/uncomment to use another maze.

Names

It's generally discouraged to use single letter variables. This makes your code hard to read. The only exceptions are i, j in for loop indices and some really specific cases.

So replace _ with _:
r -> maxRow
c -> maxCol
i -> row
j -> col
q -> queue
spare -> (removed completely as it is unused)

class Maze

Your Maze class does not actually represent a maze. It represents a single square in a maze. So I would rename it to Square or Tile to better convey its purpose.

Copy paste

You have this piece of code exactly 4 times:

    if (isPresent(row + 1, col, maxRow, maxCol) && maze[row + 1][col].flag != true)//check down of current cell
    {
        if (m[row + 1][col] == 0)//if there is path, add it to queue
        {
            maze[row + 1][col].distance += 1 + d;
            queue.add(maze[row + 1][col]);
            maze[row][col].flag = true;
        }
        if (m[row + 1][col] == 1 && maze[row + 1][col].flag == false && loop == 0)//if there is no path, see if breaking the wall gives a path.
        {
            int test = solveMaze(m, row + 1, col, 1);
            if (test > 0) {
                test += d + 1;
                min = (test < min) ? test : min;
            }
            //  maze[i+1][j].flag=true;
        }
    }

The only difference are the indices. Wouldn't it be nice if you could extract this into a method instead?

To do this cleanly (without passing everything as parameters) you might want to refactor the entire class. I think it would be a decent idea to have some fields inside a MazeSolver that represent the current state of the solution. Like for example the queue the maze perhaps even the current minimum distance?

Result variable?

If I understood most of your code correctly your Maze[][] array already keeps track of the distance to reach that square. Doesn't this mean you could just return maze[maxRow-1][maxCol-1].distance?

Perhaps some logic needs to be changed to also handle passing through a wall though. I didn't fully understand how your code handled this cleanly (mostly because it didn't give the correct answer either).