Java BFS solution with Queue, standard BFS 15ms(beats 85.71%)


  • 4
    Y
    public class Solution {
      public class Element {
        int direction;
        int row, col;
        String moves;
    
        Element(int row, int col, String moves, int direction) {
          this.row = row;
          this.col = col;
          this.moves = moves;
          this.direction = direction;
        }
      }
    
      public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        //initialization
        int m = maze.length, n = maze[0].length;
        Queue<Element> path = new LinkedList<>();
        char[] directions = {'d', 'l', 'r', 'u'};
        int[] deltaRow = {1, 0, 0, -1};
        int[] deltaCol = {0, -1, 1, 0};
        boolean[][][] visited = new boolean[m][n][4];
    
        //add start point
        for (int i = 0; i < 4; i++) {
          int row = ball[0] + deltaRow[i], col = ball[1] + deltaCol[i];
          if (row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0) {
            path.add(new Element(row, col, String.valueOf(directions[i]), i));
          }
        }
    
        while (!path.isEmpty()) {
          Element top = path.poll();
          visited[top.row][top.col][top.direction] = true;
          if (top.row == hole[0] && top.col == hole[1]) {
            return top.moves;
          }
          //go with same direction
          int nextRow = top.row + deltaRow[top.direction];
          int nextCol = top.col + deltaCol[top.direction];
          if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && maze[nextRow][nextCol] == 0) {
            //no hit wall
            if (!visited[nextRow][nextCol][top.direction]) {
              path.offer(new Element(nextRow, nextCol, top.moves, top.direction));
            }
          } else {
            //hit the wall, change direction
            for (int direction = 0; direction < 4; direction++) {
              if (direction != top.direction) {
                nextRow = top.row + deltaRow[direction];
                nextCol = top.col + deltaCol[direction];
                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && maze[nextRow][nextCol] == 0
                    && !visited[nextRow][nextCol][direction]) {
                  path.offer(new Element(nextRow, nextCol, top.moves + directions[direction], direction));
                }
              }
            }
          }
        }
        return "impossible";
      }
    }
    

  • 1

    I don't understand why your bfs solution is faster than mine. It seems my solution is more like Dijkstra's Algorithm. And it should be faster I think, but it turns out your solution is faster. Can you give me some hints about that?

    public class Solution {
        int[][] dirs = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
        char[] dirc = {'d', 'l', 'r', 'u'};
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int m = maze.length, n = maze[0].length;
            String minS = null;
            int min = Integer.MAX_VALUE;
            
            int[][] map = new int[m][n]; // min distance till this node
            for (int i = 0; i < m; i++) Arrays.fill(map[i], Integer.MAX_VALUE);
            
            Node start = new Node(ball[0], ball[1], 0, ""); // start point
            PriorityQueue<Node> q = new PriorityQueue();
            q.add(start);
            
            boolean[][] vis = new boolean[m][n]; // visited nodes
            while (!q.isEmpty()) {
                // extract min, get the cur position
                Node cur = q.poll();
                if (cur.x == hole[0] && cur.y == hole[1]) break;
                vis[cur.x][cur.y] = true;
                // try 4 dirs
                for (int d = 0; d < 4; d++) {
                    int x = cur.x, y = cur.y;
                    
                    // start point, or get the end point
                    while (x + dirs[d][0] < m && x + dirs[d][0] >= 0 && y + dirs[d][1] < n && y + dirs[d][1] >= 0
                           && maze[x + dirs[d][0]][y + dirs[d][1]] != 1) {
                        x += dirs[d][0];
                        y += dirs[d][1];
                        if (vis[x][y] || (x == hole[0] && y == hole[1])) break;
                    }
                    int step = cur.step + Math.abs(x - cur.x) + Math.abs(y - cur.y);
                    if (vis[x][y] || step > map[x][y]) continue;
                    // update distance
                    map[x][y] = step;
                    // next node
                    Node next = new Node(x, y, step, cur.route + dirc[d]);
                    
                    // reach the end
                    if (x == hole[0] && y == hole[1]) {
                        if (step == min && (minS == null || next.route.compareTo(minS) < 0)) {
                            minS = next.route;
                        } else if (step < min) {
                            min = step;
                            minS = next.route;
                        }
                        // if reach the end in this direction, we don't need to try other directions
                        break;
                    }
                    
                    q.add(next);
                }
            }
            return minS == null ? "impossible" : minS;
        }
        
        class Node implements Comparable<Node> {
            int x, y, step;
            String route; // a string formed by directions along the way
            public Node(int x, int y, int step, String route) {
                this.x = x;
                this.y = y;
                this.step = step;
                this.route = route;
            }
    
            public int compareTo(Node that) {
                return this.step - that.step;
            }
        }
    }
    

  • 2
    Y

    @zhugejunwei I think the complexity of the two algorithms are not easy to analyze, since it depends on the actual graph. The point is, I use standard BFS, which explores every possible path equally. If you visually think about the process(I am lazy and do not know how to draw a nice picture or simulation animation), it is like a spread when hitting the wall.

    Your algorithm is brilliant btw, it is a greedy approach, Dijkstra's algorithm always choose the shortest unvisited point, but in the problem, you need to first find how far is the next node from the current node, which is not given(different from Dijkstra where the distance from point to point is given). I would imagine a simple scenario that your algorithm is slower than mine where, a simple case with no wall in the graph, the hole is 10 steps above the starting point, but first you go down for 1000 steps to hit the wall, then try to find another way. The thing is your algorithm always goes until hit the wall, so it can cause some waste, scenarios like for example, you have 8 nodes in pqueue, and the 8th node is the best answer, you explores the first 7 nodes, and they take a lot of time since they just can go straight for one direction for a long distance.

    But I agree, there are scenarios that your algorithm is faster, basically the difference is DFS or BFS, for a random graph, I am not sure which one is better, I would imagine it would be similar.


  • 0

    @yanzhan2 Thanks for your detailed explanation. But there is one line in my solution that can simply detect the hole point when the ball is passing by: if (vis[x][y] || (x == hole[0] && y == hole[1])) break;. So it will not go down for 1000 steps to hit the wall, it will instead stop right away. So the example case you mentioned I think it's not a problem.

    Maybe it's because the comparison operation that slow this solution down? I know some operations in LeetCode are quite slow.

    But anyway, I think this would not be a big problem in an interview I think.


  • 0
    Y

    @zhugejunwei I agree, some small operations can affect the running time a lot. But that's not what I mean though, what I thought is, you have a for loop to try the 4 directions, and following the order of d, l, r, u, and you use DFS to go into the direction until it hits the boundary. My example was, if the hole is above the starting point, and you first go down until hits the wall in the while loop, that is what I mean by 1000 steps.


  • 0

    @yanzhan2 Oh, I see. Yes, in that case it can be slower. Thanks.


Log in to reply
 

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