Similar to The Maze II. Easy-understanding Java bfs solution.


  • 16
    C

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

    We just need to implement Comparable of Point, and record the route of every point.

    public class Solution {
        class Point implements Comparable<Point> {
            int x,y,l;
            String s;
            public Point(int _x, int _y) {x=_x;y=_y;l=Integer.MAX_VALUE;s="";}
            public Point(int _x, int _y, int _l,String _s) {x=_x;y=_y;l=_l;s=_s;}
            public int compareTo(Point p) {return l==p.l?s.compareTo(p.s):l-p.l;}
        }
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int m=maze.length, n=maze[0].length;
            Point[][] points=new Point[m][n];
            for (int i=0;i<m*n;i++) points[i/n][i%n]=new Point(i/n, i%n);
            int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
            String[] ds=new String[] {"u","r","d","l"};
            PriorityQueue<Point> list=new PriorityQueue<>(); // using priority queue
            list.offer(new Point(ball[0], ball[1], 0, ""));
            while (!list.isEmpty()) {
                Point p=list.poll();
                if (points[p.x][p.y].compareTo(p)<=0) continue; // if we have already found a route shorter
                points[p.x][p.y]=p;
                for (int i=0;i<4;i++) {
                    int xx=p.x, yy=p.y, l=p.l;
                    while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0 && (xx!=hole[0] || yy!=hole[1])) {
                        xx+=dir[i][0];
                        yy+=dir[i][1];
                        l++;
                    }
                    if (xx!=hole[0] || yy!=hole[1]) { // check the hole
                        xx-=dir[i][0];
                        yy-=dir[i][1];
                        l--;
                    }
                    list.offer(new Point(xx, yy, l, p.s+ds[i]));
                }
            }
            return points[hole[0]][hole[1]].l==Integer.MAX_VALUE?"impossible":points[hole[0]][hole[1]].s;
        }
    }
    

  • 0

    BFS:

    1. Start from ball, adding 4 directions of it into queue(order by D->L->R->U), if it is not boundary or 1.
    2. Poll one path from queue while the queue has path:
      ...a) if the path reach hole, return the path.
      ...b) follow the previous direction, adding it to queue.
      ...c) If the next cell on the direction is boundary or 1, adding other two directions into queue.
      public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        if(maze.length == 0) return "";
        int m = maze.length, n = maze[0].length;
        Queue<Cell> q = new LinkedList();
        
        int bx = ball[0], by = ball[1];
        if(!isTurn(maze, bx + 1, by)) q.offer(new Cell(bx + 1, by, "d"));
        turnLeftRight(q, maze, bx, by, "");
        if(!isTurn(maze, bx - 1, by)) q.offer(new Cell(bx - 1, by, "u"));
    
        while(!q.isEmpty()){
          Cell c = q.poll();
          if(c.x == hole[0] && c.y == hole[1]) return c.path;
          char d = c.path.charAt(c.path.length() - 1);
    
          switch(d){
            case 'd':
              if(!isTurn(maze, c.x + 1, c.y)){
                q.offer(new Cell(c.x + 1, c.y, c.path));
              } else {
                if(maze[c.x][c.y] == -1) continue;
                maze[c.x][c.y] = -1;
                turnLeftRight(q, maze, c.x, c.y, c.path);
              }
              break;
            case 'l':
              if(!isTurn(maze, c.x, c.y - 1)){
                q.offer(new Cell(c.x, c.y - 1, c.path));
              } else {
                if(maze[c.x][c.y] == -1) continue;
                maze[c.x][c.y] = -1;
                turnUpDown(q, maze, c.x, c.y, c.path);
              }
              break;
            case 'r':
              if(!isTurn(maze, c.x, c.y + 1)){
                q.offer(new Cell(c.x, c.y + 1, c.path));
              } else {
                if(maze[c.x][c.y] == -1) continue;
                maze[c.x][c.y] = -1;
                turnUpDown(q, maze, c.x, c.y, c.path);
              }
              break;
            case 'u':
              if(!isTurn(maze, c.x - 1, c.y)){
                q.offer(new Cell(c.x - 1, c.y, c.path));
              } else {
                if(maze[c.x][c.y] == -1) continue;
                maze[c.x][c.y] = -1;
                turnLeftRight(q, maze, c.x, c.y, c.path);
              }
              break;
          }
        }
        return "impossible";
      }
      
      void turnLeftRight(Queue<Cell> q, int[][] maze, int x, int y, String path){
        if(!isTurn(maze, x, y - 1)) q.offer(new Cell(x, y - 1, path + "l"));
        if(!isTurn(maze, x, y + 1)) q.offer(new Cell(x, y + 1, path + "r"));      
      }
      
      void turnUpDown(Queue<Cell> q, int[][] maze, int x, int y, String path){
        if(!isTurn(maze, x + 1, y)) q.offer(new Cell(x + 1, y, path + "d"));
        if(!isTurn(maze, x - 1, y)) q.offer(new Cell(x - 1, y, path + "u"));      
      }
      
      boolean isTurn(int[][] maze, int x, int y){
        return x < 0 || x >= maze.length || y < 0 || y >= maze[0].length || maze[x][y] == 1;
      }
    
      class Cell{
        int x, y;
        String path;
        public Cell(int xx, int yy, String p){
          x = xx;
          y = yy;
          path = p;
        }
      }

  • 0
    A

    @ckcz123 What is the time complexity of the algorithm .Is it O(n^2) ?


  • 0
    S

    Hey @ckcz123 Since these questions are now locked and available in premium I want to solve them now Could you help me on this and tell me what are all the 3 questions on maze exactly ?


  • 0
    M

    @anirudhkowdeed
    Since it's very similar to Dijkstra
    points: any stoppable points and start point
    edges = any possible path between two points

    I think it will be O((edges + points) * O(points))


  • 0
    J

    how do you ensure that it is the lexicographically smallest? @ckcz123


  • 0
    M
    This post is deleted!

  • 0
    M

    @jyu332
    The compareTo in the constructor makes sure that each path stored in lexicographically smallest when the lengths are same


  • 0
    F

    My solution takes me 4 hours.... Thanks for my insistence...

    class Solution {
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{ball[0], ball[1]});
            int m = maze.length, n = maze[0].length;
            int[][] dir = new int[][]{{1, -1, 0, 0}, {0, 0, 1, -1}};
            String[] pa = new String[]{"d", "u", "r", "l"};
            int[][] dp = new int[m][n];
            String[][] dpPath = new String[m][n];
            for (int[] d: dp) {
                Arrays.fill(d, Integer.MAX_VALUE);
            }
            for (String[] d: dpPath) {
                Arrays.fill(d, "z");
            }
            dp[ball[0]][ball[1]] = 0;
            dpPath[ball[0]][ball[1]] = "";
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int row = cur[0];
                    int col = cur[1];
                    String path = dpPath[row][col];
                    int dist = dp[row][col];
                    path += pa[i];
                    while (row >= 0 && row < m && col >= 0 && col < n && maze[row][col] != 1) {
                        if (row == hole[0] && col == hole[1]) {
                            break;
                        }
                        row += dir[0][i];
                        col += dir[1][i];
                        dist++;
                    }
                    if (row != hole[0] || col != hole[1]) {
                        row -= dir[0][i];
                        col -= dir[1][i];
                        dist--;
                    }
                    if (row == cur[0] && col == cur[1]) {
                        continue;
                    }
                    if (dist <= dp[row][col]) { 
                        if (dist < dp[row][col]) {
                            dp[row][col] = dist;
                            dpPath[row][col] = path;
                        } else if (path.compareTo(dpPath[row][col]) < 0) {
                            dpPath[row][col] = path;
                        }
                        queue.offer(new int[]{row, col});
                    }
                }
            }
            return dpPath[hole[0]][hole[1]].equals("z")? "impossible": dpPath[hole[0]][hole[1]];
        }
    }
    

  • 0
    V

    It is not necessary to use a PriorityQueue. By all means, you cannot stop searching once the hole is reached, as the local optimum may not be a global optimum here. A point that is marked as "explored" in Dijkstra's algorithm is not completely "explored" as there might be another path that reaches this with equal distance but with a smaller lexicographical order (i.e., "ul" vs. "lu"). So anyway, you have to search all the possible paths that can reach the hole. So using a normal queue would suffice.


Log in to reply
 

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