LeetCode 499 - The Maze III

Leetcode 490, 505 - The Maze I,III
http://bookshadow.com/weblog/2017/01/29/leetcode-the-maze-ii/

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up (u), down (d), left (l) or right (r), but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a hole in this maze. The ball will drop into the hole if it rolls on to the hole.

Given the ball position, the hole position and the maze, your job is to find out how the ball could drop into the hole by moving shortest distance in the maze. The distance is defined by the number of empty spaces the ball go through from the start position (exclude) to the hole (include). Output the moving directions by using 'u', 'd', 'l' and 'r'. Since there may have several different shortest ways, you should output the lexicographically smallest way. If the ball cannot reach the hole, output "impossible".

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The ball and hole coordinates are represented by row and column indexes.

Example 1

Input 1: a maze represented by a 2D array

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

Input 2: ball coordinate (rowBall, colBall) = (4, 3)
Input 3: hole coordinate (rowHole, colHole) = (0, 1)

Output: "lul"
Explanation: There are two shortest ways for the ball to drop into the hole.
The first way is left -> up -> left, represented by "lul".
The second way is up -> left, represented by 'ul'.
Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' < 'u'. So the output is "lul".

Example 2

Input 1: a maze represented by a 2D array

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

Input 2: ball coordinate (rowBall, colBall) = (4, 3)
Input 3: hole coordinate (rowHole, colHole) = (3, 0)
Output: "impossible"
Explanation: The ball cannot reach the hole.

Note:

1. There are only one ball and one hole in the maze.
2. The ball and hole will only exist in the empty space, and they will not at the same position initially.
3. The given maze doesn't contain border (like the red rectangle in the example pictures), but you should assume the border of the maze are all walls.
4. The maze contains at least 2 empty spaces, and the length and width of the maze won't exceed 30.

https://github.com/Turingfly/leetcode/blob/master/LeetCode/src/bfs/_499_TheMazeIII.java
http://www.cnbolgs.com/grandyang/p/6746528.html这道题在之前的两道The Maze II和The Maze的基础上又做了些改变，在路径中间放了个陷阱，让球在最小步数内滚到陷阱之中，此时返回的并不是最小步数，而是滚动的方向，用u, r, d, l 这四个字母来分别表示上右下左，而且在步数相等的情况下，让我们返回按字母排序小的答案。相对于迷宫二那题来说，难度是增加了一些，但我们还是可以借鉴之前那道题的思路，我们还是需要用一个二位数组dists，其中dists[i][j]表示到达(i,j)这个位置时需要的最小步数，我们都初始化为整型最大值，在后在遍历的过程中不断用较小值来更新每个位置的步数值。我们还需要用一个哈希表来建立每个位置跟滚到该位置的方向字符串之间的映射，这里我们用一个trick，将二维坐标转(i,j)为一个数字i*n+j，这实际上就是把二维数组拉成一维数组的操作，matlab中很常见的操作。还有需要注意的是，一滚到底的操作需要稍作修改，之前我们都是一直滚到墙里面或者界外才停止，然后做退一步处理，就是小球能滚到的位置，这里我们滚的时候要判断陷阱，如果滚到了陷阱，那么我们也停下来，注意这时候不需要做后退一步处理。然后我们还是比较当前步数是否小于dists中的原有步数，小于的话就更新dists，然后更新哈希表中的映射方向字符串，然后对于不是陷阱的点，我们加入队列queue中继续滚。另一点跟迷宫二不同的之处在于，这里还要处理另一种情况，就是当最小步数相等的时候，并且新的滚法的方向字符串的字母顺序要小于原有的字符串的时候，我们也需要更新哈希表的映射，并且判断是否需要加入队列queue中

预处理 + 单源最短路

首先预处理迷宫maze中各点坐标向四个方向运动最终可以达到的坐标，用数组dmap记录。

例如dmap[(3, 2)]['u']表示从坐标(3, 2)出发向上运动最终可以到达的位置。

利用数组bmap记录迷宫中各点坐标到小球初始位置的最短距离dist与最短路径path。

维护队列queue，初始将(ball, 0, '')加入queue（坐标，距离，路径）

记当前坐标为p，从p出发，分别向u, d, l, r四个方向扩展并更新下一个坐标np的最短距离与路径，保存在bmap中。

如果np得到更新，则将np加入队列；重复此过程直到queue为空

返回bmap[hole]

下面的解法采用Dijkstra算法，比上面的解法效率更优
X. BFS
https://discuss.leetcode.com/topic/77361/short-clean-and-straight-forward-bfs-solution-with-priorityqueue

The idea is just using BFS with a PriorityQueue(dijkstra's algorithm), PriorityQueue polls out the Coordinate with the minimum distance, if there are two with same distance, we compare their lexicographical order, by this way, we can ensure that we get the lexicographically smallest way in the end.

    class Coordinate implements Comparable<Coordinate> {
        int x, y, dist;
        String moves;

        public Coordinate(int x, int y, int dist, String moves) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.moves = moves;
        }
        
        public int compareTo(Coordinate that) {
            if (this.dist != that.dist)     return this.dist - that.dist;
            return this.moves.compareTo(that.moves);
        }
    }
    
    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;

        boolean[][] visited = new boolean[m][n];
        
        PriorityQueue<Coordinate> pq = new PriorityQueue<>();
        pq.add(new Coordinate(ball[0], ball[1], 0, ""));
        
        while(!pq.isEmpty()) {
            Coordinate curr = pq.poll();
            
            if (curr.x == hole[0] && curr.y == hole[1]) {
                return curr.moves;
            }
            
            if (!visited[curr.x][curr.y]) {
                visited[curr.x][curr.y] = true;
                for (int direction = 0; direction < 4; direction++) {
                    Coordinate next = moveForward(maze, curr, direction, hole);
                    pq.add(new Coordinate(next.x, next.y, next.dist, next.moves + dirc[direction]));
                }
            }
        }
        return "impossible";
    }
    
/*
    Start from current position move forward in one direction until hit the wall, return the last position before hitting the wall
*/
    private Coordinate moveForward(int[][] maze, Coordinate curr, int direction, int[] hole) {
        int m = maze.length, n = maze[0].length;
        int nx = curr.x, ny = curr.y, dis = curr.dist;
        while (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[nx][ny] == 0) {
            nx += dirs[direction][0];
            ny += dirs[direction][1];
            dis++;
            if (nx == hole[0] && ny == hole[1]) {
                return new Coordinate(nx, ny, dis, curr.moves);
            }
        }
        // back up one step from wall
        nx -= dirs[direction][0];
        ny -= dirs[direction][1];
        dis--;
        return new Coordinate(nx, ny, dis, curr.moves);
    }

https://discuss.leetcode.com/topic/77474/similar-to-the-maze-ii-easy-understanding-java-bfs-solution

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

    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;
    }

https://discuss.leetcode.com/topic/77123/java-bfs-solution-with-queue-standard-bfs-15ms-beats-85-71

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.

 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.

  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";
  }

https://discuss.leetcode.com/topic/77074/clear-java-accepted-dfs-solution-with-explanation
http://144.168.59.81:8081/2017/02/01/leetcode_499/

Each time, first add the direction to the path, and then go with that direction, checking for hole along the way. When hit a wall, try to turn, and go with the new direction. For the starting point, don't "go", jump directly to "turn" part.

    int min; //min distance to hole
    String minS; //min distance's path string
    int[] hole;
    int[][] maze; 
    int[][] map; //shortest distant traveling from ball to this point
    int[][] dirs = {{0,1},{-1,0},{1,0},{0,-1}}; //r, u, d, l
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        this.min = Integer.MAX_VALUE; 
        this.minS = null;
        this.hole = hole; 
        this.maze = maze; 
        this.map = new int[maze.length][maze[0].length];
        for(int i = 0; i<map.length; i++) Arrays.fill(map[i], Integer.MAX_VALUE); 
        move(ball[0], ball[1], 0, "", -1);
        return (minS==null) ? "impossible" : minS;
    }
    
    private void move(int r, int c, int cnt, String path, int dir){//dir is a index of dirs 
        if(cnt > min || cnt > map[r][c]) return; //not a shortest route for sure 
        int rr = r;
        int cc = c;
        if(dir!=-1){//if not from start point 
            //add path 
            if(dir==0) path+='r';
            else if(dir==1) path+='u';
            else if(dir==2) path+='d';
            else path+='l';
    
            //roll along dir 
            while(rr>=0 && rr<maze.length && cc>=0 && cc<maze[0].length && maze[rr][cc]==0){
                map[rr][cc] = Math.min(map[rr][cc], cnt); 
                if(rr==hole[0] && cc==hole[1]){//check hole
                    if(cnt==min && path.compareTo(minS)<0){
                        minS=path;
                    }else if(cnt<min){
                        min = cnt; 
                        minS = path; 
                    }
                    return; 
                }
                rr += dirs[dir][0];//move along dir
                cc += dirs[dir][1];
                cnt++;
            }
            rr -= dirs[dir][0];//[rr,cc] is wall, need to walk back 1 step
            cc -= dirs[dir][1];
            cnt--;
        }
        
        //hit wall (or start) -> try to turn
        for(int i = 0; i<dirs.length; i++){
            if(dir == i || dir == (3-i)) continue;//dont keep going this dir and dont go back
            int newR = rr + dirs[i][0];
            int newC = cc + dirs[i][1];
            if(newR>=0 && newR<maze.length && newC>=0 && newC<maze[0].length && maze[newR][newC]==0){//can go
                move(rr, cc, cnt, path, i);
            }
        }
    }

I really appreciated your int[][] map and use index of int[][] dirs to represent r,u,l,d, it simplified many works for me.

    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();
            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]);
                
               // System.out.println(next.route);  /// this damn line!!! slowed my solution...
                
                // 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 boolean equals(Node a, Node b) {
            return a.x == b.x && a.y == b.y;
        } 
        
        public int compareTo(Node that) {
            return this.step - that.step;
        }
    }

X. DFS
https://blog.csdn.net/magicbean2/article/details/78727575
也就是在搜索的过程中维护一个截止当前的最优解（需要包含路径字符串已经路径长度）。在当前的位置上沿着当前方向一直前进，直到遇到障碍。如果在前进的过程中遇到了洞，那么就更新结果。否则当走到尽头的时候就改变方向（只能右转或者左转，不可继续或者逆向返回）。我们在深度优先搜索的过程中，保持down->left->right->up这样一个方向，可以保证字典序最小的结果最小被获得。

https://www.codetd.com/article/3730430

    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if(maze.length == 0 || maze[0].length == 0) return false;
        if(start[0] == destination[0] && start[1] == destination[1]) return true;
        
        m = maze.length; n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        return dfs(maze, start, destination, visited);
    }
    int m, n;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private boolean dfs(int[][] maze, int[] cur, int[] dest, boolean[][] visited) {
        // already visited
        if(visited[cur[0]][cur[1]]) return false;
        // reach destination
        if(Arrays.equals(cur, dest)) return true;
        
        visited[cur[0]][cur[1]] = true;
        for(int[] dir : dirs) {
            int nx = cur[0], ny = cur[1];
            while(notWall(nx + dir[0], ny + dir[1]) && maze[nx+dir[0]][ny+dir[1]] != 1) {
                nx += dir[0]; ny += dir[1];
            }
            if(dfs(maze, new int[] {nx, ny}, dest, visited)) return true;
        }
        return false;
    }
    
    private boolean notWall(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

https://discuss.leetcode.com/topic/77074/clear-java-accepted-dfs-solution-with-explanation/3

Each time, first add the direction to the path, and then go with that direction, checking for hole along the way. When hit a wall, try to turn, and go with the new direction. For the starting point, don't "go", jump directly to "turn" part.

    int min; //min distance to hole
    String minS; //min distance's path string
    int[] hole;
    int[][] maze; 
    int[][] map; //shortest distant traveling from ball to this point
    int[][] dirs = {{0,1},{-1,0},{1,0},{0,-1}}; //r, u, d, l
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        this.min = Integer.MAX_VALUE; 
        this.minS = null;
        this.hole = hole; 
        this.maze = maze; 
        this.map = new int[maze.length][maze[0].length];
        for(int i = 0; i<map.length; i++) Arrays.fill(map[i], Integer.MAX_VALUE); 
        
        move(ball[0], ball[1], 0, "", -1);
        return (minS==null) ? "impossible" : minS;
    }
    
    private void move(int r, int c, int cnt, String path, int dir){//dir is a index of dirs 
        if(cnt > min || cnt > map[r][c]) return; //not a shortest route for sure 
        if(dir!=-1){//if not from start point 
            //add path 
            if(dir==0) path+='r';
            else if(dir==1) path+='u';
            else if(dir==2) path+='d';
            else path+='l';
    
            //roll along dir 
            while(r>=0 && r<maze.length && c>=0 && c<maze[0].length && maze[r][c]==0){
                map[r][c] = Math.min(map[r][c], cnt); 
                if(r==hole[0] && c==hole[1]){//check hole
                    if(cnt==min && path.compareTo(minS)<0){
                        minS=path;
                    }else if(cnt<min){
                        min = cnt; 
                        minS = path; 
                    }
                    return; 
                }
                r += dirs[dir][0];
                c += dirs[dir][1];
                cnt++;
            }
            r -= dirs[dir][0];//[r,c] is wall, need to walk back 1 step
            c -= dirs[dir][1];
            cnt--;
        }
        
        //hit wall (or start) -> try to turn
        for(int i = 0; i<dirs.length; i++){
            if(dir == i) continue;//dont keep going
            if(dir == (3-i)) continue;//dont go back
            int newR = r + dirs[i][0];
            int newC = c + dirs[i][1];
            if(newR>=0 && newR<maze.length && newC>=0 && newC<maze[0].length && maze[newR][newC]==0){//can go
                move(r, c, cnt, path, i);
            }
        }
    }

    int minStep;
    int m, n;
    String res;
    int[][] dirs = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    String[] dirc = {"d", "r", "l", "u"}; // 0123
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        this.m = maze.length; 
        this.n = maze[0].length;
        this.minStep = Integer.MAX_VALUE;
        this.res = null;
        boolean[][] vis = new boolean[m][n];
        vis[ball[0]][ball[1]] = true;
        
        dfs(ball[0], ball[1], maze, hole, vis, "", 0);
        
        return res == null ? "impossible" : res;
    }
    
    private void dfs(int i, int j, int[][] maze, int[] hole, boolean[][] vis, String route, int step) {
        if (step > minStep) return;
        if (i == hole[0] && j == hole[1]) {
            if (step == minStep && route.compareTo(res) < 0) {
                res = route;
            } else if (step < minStep) {
                minStep = step;
                res = route;
            }
            vis[i][j] = false;
            return;
        }
        
        for (int d = 0; d < 4; d++) {
            // roll to the wall
            int x = i, y = j;
            while (x + dirs[d][0] >= 0 && x + dirs[d][0] < m && y + dirs[d][1] >= 0 && y + dirs[d][1] < n 
                && maze[x + dirs[d][0]][y + dirs[d][1]] != 1) {
                x += dirs[d][0];
                y += dirs[d][1];
                if (x == hole[0] && y == hole[1] || vis[x][y])  break;
            }
            if (!vis[x][y] && maze[x][y] == 0) {
                vis[x][y] = true;
                dfs(x, y, maze, hole, vis, route + dirc[d], step + Math.abs(x - i) + Math.abs(y - j));
                vis[x][y] = false;
            }
        }
    }