Java BFS solution


  • 4

    I'm sure there is some way to speed up the search :)
    I tried checking if the destination exists on the path while the ball is rolling before it hits the wall, if the destination doesn't have any wall around, then it's definitely not able to stop there. But it didn't speed up the runtime :(
    Look forward to some smart optimized solutions!

    public class Solution {
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m = maze.length, n = maze[0].length;
            boolean[][] visited = new boolean[m][n];
            int[] dx = new int[]{0, -1, 0, 1};
            int[] dy = new int[]{1, 0, -1, 0};
            
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(start);
            visited[start[0]][start[1]] = true;
            
            while (!queue.isEmpty()) {
                int[] curPos = queue.poll();
                if (curPos[0] == destination[0] && curPos[1] == destination[1]) {
                    return true;
                }
                // try four direction until it hits the wall
                for (int direction = 0; direction < 4; direction++) {
                    int nx = curPos[0], ny = curPos[1];
                    while (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 0) {
                        nx += dx[direction];
                        ny += dy[direction];
                    }
                    
                    //back one step
                    nx -= dx[direction];
                    ny -= dy[direction];
                    
                    if (!visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
            return false;
        }
    }
    

  • 0
    S

    Hey I tried to optimize in a similar manner as you did and it seems to have a slight edge in terms of runtime. Added a helper call as below:

    int row, col;
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    ...
            if (!stoppable(maze, destination[0], destination[1])) return false;
    ...
    }
    
    private boolean stoppable(int[][] maze, int i, int j) {
            return i == 0 || i == row-1 || j == 0 || j == col-1 || 
            maze[i-1][j] == 1 || maze[i+1][j] == 1 || maze[i][j-1] == 1 || maze[i][j+1] == 1;
        }
    

    The idea is to pre-check whether the destination is next to a wall before rolling the ball, which I originally read from a post in the Maze II, cuz I think checking at every step while rolling might not be quite efficient.

    Another possible optimization is to alternate the direction to roll the ball, (i.e. roll it vertically from current spot and horizontally from next spot and so on...) except at the starting point, since generally in the same direction it's either a wall you just hit or going back to where you came from (which is already marked visited, but this trick still seems to be a little faster in practice).

    Together the above two yield a runtime of 9ms at best, which is a bit better than nothing. I have the code in my own post (second chunk) but there isn't much explanation. You code looks neat btw!


  • 0
    M

    //back one step
    nx -= dx[direction];
    ny -= dy[direction];
    Why back one step ? You hit a wall and should continue from there right ? What am I missing ?

    Thanks


  • 0
    Z

    @tankztc Thanks for the solution! Maybe you can check whether the destination is reached before pushing a point into the queue. This should save one round search in BFS.


  • 0
    F

    What's the time complexity of it?
    I think both the time and space complexity are O(mn). Correct me if I am wrong...The worst case the ball will completely traversal the maze.


  • 0
    C

    @FF_Ti can you please explain why the time complexity is o(m*n)?
    consider this very simple example
    1 0
    d 0
    1 0
    1 s

    it starts at (3,0) and moves to (0, 1) then from (0, 1) it moves back to (3,0).
    it visits cells between (3,0) and (0, 1) twice ..


  • 0
    F

    @crackinginteview9912
    Look this example:
    s->0->0->0
    0<-0<-0<-0
    0->0->d 1
    The worst case is the ball will traverse the whole maze. So the worst case time complexity is O(m*n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.