[dfs]Beat 99% without additional visited matrix better than bfs solution


  • 0
    F

    The reason why bfs is better than dfs is that if the nodes adjacent with min node are less than min node, then could directly visit these nodes without putting them into priority queue to find the next
    candidate nodes needs to be visited. This process will save the time for putting new node into PriorityQueue.

    class Point {
            int x;
            int y;
            int h;
            Point(int i, int j, int height) {
                x = i;
                y = j;
                h = height;
            }
        }
        public static final int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        int water = 0, visitedValue = -1, counter = 0;
        PriorityQueue<Point> queue = null;
        public int trapRainWater(int[][] heightMap) {
            if (heightMap.length < 3 || heightMap[0].length < 3) return 0;
            queue = new PriorityQueue<>(1, new Comparator<Point>(){
                @Override
                public int compare(Point p1, Point p2) {
                    return p1.h - p2.h;
                }
            });
            int m = heightMap.length, n = heightMap[0].length;
            for (int i = 0; i < m; i++) {
                queue.add(new Point(i, 0, heightMap[i][0]));
                queue.add(new Point(i, n-1, heightMap[i][n-1]));
                heightMap[i][0] = visitedValue;
                heightMap[i][n-1] = visitedValue;
            }
            
            for (int j = 1; j < n-1; j++) {
                queue.add(new Point(0, j, heightMap[0][j]));
                queue.add(new Point(m-1, j, heightMap[m-1][j]));
                heightMap[0][j] = visitedValue;
                heightMap[m-1][j] = visitedValue;
            }
            
            Point p = null;
            int x, y;
            counter = (m-1)*(n-1);
            while(queue.size() > 0 && counter > 0) {
                p = queue.poll();
                dfs(p, heightMap, 0, 0, p.h);
            }
            return water;
        }
        
        private void dfs(Point p, int[][] heightMap, int i, int j, int min) {
            int curX = (p != null? p.x : i);
            int curY = (p != null? p.y : j);
            int x, y;
            for (int[] dir: dirs) {
                x = curX+dir[0];
                y = curY+dir[1];
                if (x < 0 || x >= heightMap.length || y < 0 || y >= heightMap[0].length || heightMap[x][y] == visitedValue) continue;
                if (heightMap[x][y] <= min) {
                    water += (min-heightMap[x][y]);
                    heightMap[x][y] = visitedValue;
                    counter--;
                    dfs(null, heightMap, x, y, min);
                } else {
                    queue.offer(new Point(x, y, heightMap[x][y]));
                    heightMap[x][y] = visitedValue;
                    counter--;
                }
            }
        }

Log in to reply
 

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