Could u use DFS here too? And would it be worse/better?
Does this question only want a valid step count or minimum step count from an “exit gate” cell? If latter, then solution will change…based on the below thought:
A cell is reachable via multiple "exit gate" cells and while processing, the cell is first processed for a path reachable from an "exit gate" cell which is not the closest. Since, we will update the value from "INF" to some integer, later when we traverse the same cell via a closer "exit gate", we would not update the cell as its no longer "INF".My interpretation was output should be min across all gates.
I solved by doing BFS from every exit gate. In my solution, I update map[r][c] with min(map[r][c], dist in bfs).
I agree with the reference answer that it’s better to add all gates to the queue and do BFS once.
After reviewing, I finally understand the genius in the provided solution:
By initializing queue with all gates, we are search (fan out) from each gate, which means each tile must be updated with steps from the closest gate.
Proof by counterexample:
Suppose a tile is not marked by closest gate, ex. marked with 2 but closest gate is 1 away. This would be impossible as closest gate would have reached it in 1 step, marked 1, and visited ensured the tile is not visited again.
Since the board is finite, whichever you prefer. However, if the board was infinite, BFS would be the better choice since DFS can potentially lead to infinite recursion.
The solution achieves the same result. The provided solution just performs BFS from all the exits altogether rather than iteratively performing BFS from each exit.
from typing import List
from collections import deque
INT_MAX = 2147483647
def map_gate_distances(dungeon_map: List[List[int]]) → List[List[int]]:
res = []
r_nums = len(dungeon_map)
c_nums = len(dungeon_map[0])
q = deque([])
def get_neighbor(coord):
row, col = coord
delta_row = [-1, 0, 1, 0]
delta_col = [0, 1, 0, -1]
for i in range(len(delta_row)):
r = row + delta_row[i]
c = col + delta_col[i]
yield((r, c))
def bfs(dungeon_map, r_nums, c_nums):
for i in range(r_nums):
for j in range(c_nums):
if dungeon_map[i][j] == 0:
q.append((i,j))
while(len(q) > 0):
node = q.popleft()
curRow, curCol = node[0], node[1]
for neighbor in get_neighbor(node):
r, c = neighbor
if r < 0 or c < 0 or r >= r_nums or c >= c_nums or dungeon_map[r][c] != INT_MAX:
continue
dungeon_map[r][c] = dungeon_map[curRow][curCol] + 1
q.append(neighbor)
return dungeon_map
return bfs(dungeon_map, r_nums, c_nums)
Actually, both methods would stack overflow. BFS function stack call would overflow since the first level of the tree is infinite, DFS function stack call would overflow going either of the 4 directions, infinitely.
But both is indeed possible on finite board which the test cases only capture.
public static List<List> mapGateDistances(List<List> dungeonMap) {
List exits = new ArrayList();
for (int i = 0; i < dungeonMap.size(); i++) {
for (int j = 0; j < dungeonMap.get(i).size(); j++) {
if (dungeonMap.get(i).get(j) == 0) {
exits.add(new Point(i, j));
}
}
}
for (Point exit: exits) {
dfs(dungeonMap, exit, new HashSet(), 0);
}
return dungeonMap;
}
public static void dfs(List<List<Integer>> dungeon, Point p, Set<Point> visited, int count) {
if (!(p.x >= 0 && p.x < dungeon.size() && p.y >= 0 && p.y < dungeon.get(0).size())) return;
int value = dungeon.get(p.x).get(p.y);
if (value == -1) {
return;
} if (value > 0) {
dungeon.get(p.x).set(p.y, Math.min(value, count));
} else if (value == 0) {
count = 0;
}
for (Point neigh: neighbors(dungeon, p)) {
if (!visited.contains(neigh)) {
visited.add(neigh);
dfs(dungeon, neigh, visited, count + 1);
}
}
visited.remove(p);
}
public static void bfs(List<List<Integer>> dungeon, Point root) {
Queue<Point> bfs = new ArrayDeque();
Set<Point> visited = new HashSet();
bfs.add(root);
visited.add(root);
int steps = 0;
while (!bfs.isEmpty()) {
int size = bfs.size();
for (int i = 0; i < size; i++) {
Point p = bfs.remove();
int value = dungeon.get(p.x).get(p.y);
dungeon.get(p.x).set(p.y, Math.min(value, steps));
for (Point neigh: neighbors(dungeon, p)) {
if (!visited.contains(neigh)) {
bfs.add(neigh);
visited.add(neigh);
}
}
}
steps++;
}
}
public static List<Point> neighbors(List<List<Integer>> dungeon, Point p) {
List<Point> neighbors = new ArrayList();
int maxRows = dungeon.size();
int maxCols = dungeon.get(0).size();
int[][] coords = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < coords.length; i++) {
int x = p.x + coords[i][0];
int y = p.y + coords[i][1];
if (x >= 0 && x < maxRows && y >= 0 && y < maxCols) {
if (dungeon.get(x).get(y) != -1) {
neighbors.add(new Point(x, y));
}
}
}
return neighbors;
}
For better explanation of why only one BFS works check comments of https://leetcode.com/problems/walls-and-gates/solution/
def map_gate_distances(dungeon_map: List[List[int]]) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
m = len(dungeon_map)
n = len(dungeon_map[0])
destinations = []
for i in range(m):
for j in range(n):
if dungeon_map[i][j] == 0:
destinations.append([(i, j), 0])
# multi-source BFS
queue = destinations[:]
while queue:
node, dist = queue.pop(0)
neighbors = get_neighbors(node, m, n)
for neighbor in neighbors:
neighbor_i, neighbor_j = neighbor
if dungeon_map[neighbor_i][neighbor_j] == 2147483647:
dungeon_map[neighbor_i][neighbor_j] = dist + 1
queue.append([(neighbor_i, neighbor_j), dist+1])
return dungeon_map
def get_neighbors(node, m, n):
neighbors = []
directions = [(0,-1), (-1,0), (0,1), (1,0)]
for d in directions:
neighbor_i = node[0] + d[0]
neighbor_j = node[1] + d[1]
if 0 <= neighbor_i < m and 0 <= neighbor_j < n:
neighbors.append((neighbor_i, neighbor_j))
return neighbors
This is a classic “Multi-source BFS”. The idea is that you start traversing from multiple sources at the same time/in parallel (thus dump starting nodes in a queue in the beginning). as it’s BFS - you find the shortest distance quickly. Also when you think you might have a conflict of 2+ nodes trying to “mark” the cell as visited. The first node who gets access to the cell - marks it.
e.g.
[1 x y]
[x ? x]
[y x 1]
Who should change “?” bfs node from top or down? It does not matter, the one that processes it first.
I feel like we can memoize this. Imma code this up tomorrow and see
Thank you!
Why is this not explained in the solution or in other parts of the course?
What is the directions parameter in the line 18? I dont see it assigned anywhere. I am stumped, can anyone please clarify?
Hi Guys, overall Great question, I just spotted something that threw me off a little bit. The question States “for each empty space, that space is replaced by the number of steps it takes to reach ANY exit.”. The difference is only a matter of moving the visited set initialization but that could leave people wondering why the correct solution for ANY exit is not accepted since the solution is actually not considering all potential answers for the grid.
Lets look at test one for example,
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
this answer is def valid but since the question is mentioning ANY exit it could also be:
3 -1 0 1
3 2 1 -1
4 -1 2 -1
0 -1 3 4
Obviously, this is not the better answer from the two, but it is definitely a correct one based on the questions definition. So please either fix the questions clarification or fix the accepted solutions for the test cases.
Thanks!
It’s on line 4. All four directions.
Just wondering why are all of the solutions in BFS only?
Ok so I used DFS… I regret it.