Easy-understanding Java bfs solution.


  • 21
    C

    Solution of The Maze II: https://discuss.leetcode.com/topic/77472/similar-to-the-maze-easy-understanding-java-bfs-solution
    Solution of The Maze III: https://discuss.leetcode.com/topic/77474/similar-to-the-maze-ii-easy-understanding-java-bfs-solution

    A standart bfs solution.

    public class Solution {
        class Point {
            int x,y;
            public Point(int _x, int _y) {x=_x;y=_y;}
        }
        public boolean hasPath(int[][] maze, int[] start, int[] destination) {
            int m=maze.length, n=maze[0].length;
            if (start[0]==destination[0] && start[1]==destination[1]) return true;
            int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
            boolean[][] visited=new boolean[m][n];
            LinkedList<Point> list=new LinkedList<>();
            visited[start[0]][start[1]]=true;
            list.offer(new Point(start[0], start[1]));
            while (!list.isEmpty()) {
                Point p=list.poll();
                int x=p.x, y=p.y;
                for (int i=0;i<4;i++) {
                    int xx=x, yy=y;
                    while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
                        xx+=dir[i][0];
                        yy+=dir[i][1];
                    }
                    xx-=dir[i][0];
                    yy-=dir[i][1];
                    if (visited[xx][yy]) continue;
                    visited[xx][yy]=true;
                    if (xx==destination[0] && yy==destination[1]) return true;
                    list.offer(new Point(xx, yy));
                }
            }
            return false;
            
        }
    }
    

  • 0
    M

    Hi,
    May I know why visited update is not inside while loop function when rolling in same direction?


  • 7
    C

    @mingzhou1987 There may be a cross, so we cannot update while rolling.

        --->---
       |       |
       ^       v
       |       |
       ^       v
       |       |
        ---<---+--<--- o
               v
               |
    

  • 0
    G
    This post is deleted!

  • 1

    "Both the ball and the destination exist on an empty space, and they will not be at the same position initially."

    if (start[0]==destination[0] && start[1]==destination[1]) return true;

  • 2
    B

    There is no need to have a class Point.
    '''
    public class Solution {

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if (start[0] == destination[0] && start[1] == destination[1]) return true;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(start);
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        visited[start[0]][start[1]] = true;
        int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int k = 0; k < dir.length; k++) {
                int x = cur[0];
                int y = cur[1];
                while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
                    x += dir[k][0];
                    y += dir[k][1];
                }
                x -= dir[k][0];
                y -= dir[k][1];
                if (visited[x][y]) continue;
                visited[x][y] = true;
                if (x == destination[0] && y == destination[1]) return true;
                queue.offer(new int[] {x, y});
            }
        }
    

    '''

        return false;
    }
    

    }


  • 0
    Y

    great solution!


  • 1
    M

    @ckcz123
    xx-=dir[i][0];
    yy-=dir[i][1];
    Why back one step ?

    Thanks


  • 0
    C

    @mgzaki2406 Because (xx, yy) is an invalid point.


  • 0

    @ckcz123 said in Easy-understanding Java bfs solution.:

                while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
                    xx+=dir[i][0];
                    yy+=dir[i][1];
                }
    

    This is very smart move.


  • 0

    Similar Approach.

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
       boolean[][][] map = new boolean [maze.length][maze [0].length][4];
       return roll (map, maze, start, destination);
    }
       
    private int [] rowdir = { 0, 1,  0, -1 };
    private int [] coldir = { 1, 0, -1,  0 };
        
    private boolean roll (boolean[][][] map, int[][] maze, int[] start, int[] destination) {
        for (int idx = 0; idx < 4; idx ++) {
            if (!map [start [0]][start [1]][idx]) {
                map [start [0]][start [1]][idx] = true;
                if (maze [start [0]][start [1]] == 1) continue;
                int [] next = new int [] { start [0], start [1] };
                    
                while (next [0] >= 0 && next [0] < maze.length && next [1] >= 0 && next [1] < maze[0].length && maze [next [0]][next [1]] == 0)  {
                	next [0] += rowdir [idx]; next [1] += coldir [idx];
                }
                next [0] -= rowdir [idx]; next [1] -= coldir [idx];
                    
                if ((next [0] == destination [0] && next [1] == destination [1]) || (roll (map, maze, next, destination))) return true;
            }
        }
        return false;
    }
    

  • 0
    D

    I use hashset to mark visited stop position:

        public boolean hasPath(int[][] maze, int[] start, int[] destination) 
        {
            if (maze == null || maze.length == 0 || maze[0].length == 0) { return false; }
            
            int row = maze.length;
            int col = maze[0].length;
            
            // visited stop cell, convert int[]  coordinate into integer
            Set<Integer> stops = new HashSet<>();
            stops.add(start[0] * col + start[1]);
            
            Queue<int[]> que = new LinkedList<>();
            que.offer(start);
            
            int[][] dir = {{-1, 0},{1, 0},{0, -1},{0, 1}};
            while (!que.isEmpty())
            {
                int[] pos = que.poll();
                
                for (int i = 0; i < dir.length; i++)
                {
                    int r = pos[0];
                    int c = pos[1];
                    
                    // keep going until meet wall
                    while (r >= 0 && r < row && c >= 0 && c < col && maze[r][c] != 1)
                    {
                        r += dir[i][0];
                        c += dir[i][1];
                    }
                    
                    // find stop position
                    r -= dir[i][0];
                    c -= dir[i][1];
                    
                    int stop = r * col + c;
                    if (!stops.contains(stop))
                    {
                        if (r == destination[0] && c == destination[1]) { return true; }
                        
                        stops.add(stop);
                        que.offer(new int[]{r, c});
                    }
                }
            }
            return false;
        }
    

  • 0
    R

    hey guys, can anyone tell me the time complexity is what/


  • 0
    F

    @renjiandreamore 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

    I don't understand why the time complexity is O(mn).

    0 0 0 0
    s 0 0 0
    0 0 d 0
    0 0 0 0

    Consider this board and let's track the ball's traversal.
    Let's say I am moving ball to right, left, up and down.

            int[][] dir=new int[][] {{0,1},{0,-1},{-1,0},{1,0}};
    
    
    0 0 0 0
    s---->b // ball moves right
    0 0 d 0
    0 0 0 0
    
    then it moves back left 
    
    0 0 0 0
    s <---b // ball moves back left from right
    0 0 d 0
    0 0 0 0
    
    As we can see each cell is not visited just once.
    Another example .. 
    0 <-- b // ball moves to left  
    s 0 0 0
    0 0 d 0
    0 0 0 0
    
    b --> 0 
    s 0 0 0
    0 0 d 0
    0 0 0 0
    
    ball moves to right from (0,0) and it stops when it reaches (0,3).
    (0,3) is already visited thus not added to queue.
    But row 0 is visited twice when ball travels from (0,3) to (0,0) and from (0,0) to (0,3)
    So how is time complexity is O(mn)? Ball keeps traveling the reverse direction twice.

  • 0
    F

    More concise one. You don't have to check visited and if match twice.

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        queue.offer(start);
        while (!queue.isEmpty()) {
          int[] cur = queue.poll();
          if (cur[0] == destination[0] && cur[1] == destination[1]) {
            return true;
          }
          if (visited[cur[0]][cur[1]])
            continue;
          visited[cur[0]][cur[1]] = true;
          int[][] move = new int[][] {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
          for (int[] mo : move) {
            int x = cur[0], y = cur[1];
            while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
              x += mo[0];
              y += mo[1];
            }
            // Back to validate point.
            x -= mo[0];
            y -= mo[1];
            // Adding new start point.
            queue.offer(new int[] {x, y});
          }
        }
        return false;
      }
    

  • 0
    F

    @fanhai said in Easy-understanding Java bfs solution.:

    More concise one. You don't have to check visited and if match twice.

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        queue.offer(start);
        while (!queue.isEmpty()) {
          int[] cur = queue.poll();
          if (cur[0] == destination[0] && cur[1] == destination[1]) {
            return true;
          }
          if (visited[cur[0]][cur[1]])
            continue;
          visited[cur[0]][cur[1]] = true;
          int[][] move = new int[][] {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
          for (int[] mo : move) {
            int x = cur[0], y = cur[1];
            while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
              x += mo[0];
              y += mo[1];
            }
            // Back to validate point.
            x -= mo[0];
            y -= mo[1];
            // Adding new start point.
            queue.offer(new int[] {x, y});
          }
        }
        return false;
      }
    

Log in to reply
 

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