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

• 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++) {
heightMap[i][0] = visitedValue;
heightMap[i][n-1] = visitedValue;
}

for (int j = 1; j < n-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--;
}
}
}``````

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