Java - Graph: Dijkstra's Algorithm - O(n^2 m^2).


  • 0
    B

    Consider the grid spaces as nodes in a graph. The edges in this graph are from empty spaces to a stop points. When we connect two points, the two stop points must have a non-obscured path between them. Now the problem becomes finding the shortest path with the smallest lexicographical order from the ball to the hole. Dijkstra's algorithm is suitable for this kind of problem. The only add here is: during the comparisons, the path string is used as the second key besides the distance.

    The complexity is O(n^2m^2). If we count the string comparison time, it is O(n^2 m^2 (n + m))

    public class Solution {
        
        private int n;
        private int m;
        int[][][] map;
    
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            n = maze.length;
            if (n == 0) return "impossible";
            m = maze[0].length;
            if (m == 0) return "impossible";
    
            map = new int[n][m][4];
            getDist(maze, hole);
            return dijkstra(maze, ball, hole);
        }
        
        public void getDist(int[][] maze, int[] hole){
            for (int i = 0; i < n; ++i){
                int right = 0;
                for (int j = 0; j < m; ++j){
                    if (maze[i][j] == 1){
                        map[i][j][0] = -1;
                        map[i][j][2] = -1;
                    }else if (i==hole[0] && j == hole[1]){
                        map[i][j][0] = 0;
                        map[i][j][2] = 0;
                    }else{
                        map[i][j][0] = (j > 0)?(map[i][j-1][0] + 1):0;
                        map[i][j][2] = (i > 0)?(map[i-1][j][2] + 1):0;
                    }
                    
                    if (maze[n - i - 1][m - j - 1] == 1){
                        map[n - i - 1][m - j - 1][1] = -1;
                        map[n - i - 1][m - j - 1][3] = -1;
                    }else if (n - i - 1==hole[0] && m - j - 1 == hole[1]){
                        map[n - i - 1][m - j - 1][1] = 0;
                        map[n - i - 1][m - j - 1][3] = 0;
                    }else{
                        map[n - i - 1][m - j - 1][1] = (j > 0)?(map[n - i - 1][m - j][1] + 1):0;
                        map[n - i - 1][m - j - 1][3] = (i > 0)?(map[n - i][m - j - 1][3] + 1):0;
                    }
                }
            }
        }
        
        public class Node {
            int x;
            int y;
            int dist;
            String path;
            boolean done;
            
            public Node(int xval, int yval, int d){
                x = xval;
                y = yval;
                dist = d;
                path = "";
                done = false;
            }
        }
        
        public String dijkstra(int[][] maze, int[] ball, int[] hole){
            Node[][] table = new Node[n][m];
            for (int i = 0; i < n; ++i){
                for (int j = 0; j < m; ++j){
                    table[i][j] = new Node(i, j, Integer.MAX_VALUE - 1);
                    if (i == ball[0] && j == ball[1]){
                        table[i][j].dist = 0;
                    }
                }
            }
            for (int i = 0; i < n * m; ++i){
                Node next = closest(table);
                if (next.dist == Integer.MAX_VALUE-1 || (next.x == hole[0] && next.y == hole[1])) break; //only walls
                update(table, next.x, next.y, 'd');
                update(table, next.x, next.y, 'l');
                update(table, next.x, next.y, 'r');
                update(table, next.x, next.y, 'u');
                next.done = true;
            }
            
            String ret = table[hole[0]][hole[1]].path;
            if (ret.equals("")){
                ret = "impossible";
            }
            return ret;
        }
        
        private void update(Node[][] table,  int x, int y, char cd){
            int offset = 0;
            int cx = x;
            int cy = y;
            if (cd == 'l'){
                offset = map[x][y][0];
                cy -= offset;
            }else if (cd == 'r'){
                offset = map[x][y][1];
                cy += offset;
            }else if (cd == 'u'){
                offset = map[x][y][2];
                cx -= offset;
            }else if (cd == 'd'){
                offset = map[x][y][3];
                cx += offset;
            }
            Node cnode = table[cx][cy];
            Node node = table[x][y];
            if (node.dist + offset < cnode.dist){
                cnode.dist = node.dist + offset;
                cnode.path = node.path + cd;
            }else if (node.dist + offset == cnode.dist && cnode.path.compareTo(node.path + cd) > 0){
                cnode.path = node.path + cd;
            }   
        }
        
        private Node closest(Node[][] table){
            int minDist = Integer.MAX_VALUE;
            Node minNode = null;
            for (int i = 0; i < n; ++i){
                for (int j = 0; j < m; ++j){
                    if (table[i][j].done) continue;
                    if (table[i][j].dist < minDist || (table[i][j].dist == minDist && table[i][j].path.compareTo(minNode.path) < 0)){
                        minNode = table[i][j];
                        minDist = table[i][j].dist;
                    }
                }
            }
            return minNode;
        }
    }
    

Log in to reply
 

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