Oh but one cool thing about using dfs is that you get the minimums for an entire clump of empty spaces at once. With memoization, I can cut out the time to recalculate the minimum path out. Not sure how effective this is compared to BFS tho.
Approach: What I used was DFS by aggregating the minimum steps needed to get out,
and I used memoization on past spaces and their minimums. This algorithm will find
the minimum steps out for an entire empty space in one sweep. It then moves to
another empty space in the dungeon and does dfs there. Think of empty spaces as islands,
this algorithm finds the minimums out for an entire island as a time.
Hey everyone, so this is another problem where the solution is drastically different then the template, which caused me a ton of confusionā¦ Iām sure Iām not alone in this, so after a bunch of time studying and figuring out how the solution actually works, I rewrote the solution in Java that better follows the template. There are a bunch of notes included that explain the steps taken. Hopefully it helps someone out thatās stuck! Good luck with the grind everybody!!
class Solution {
public static class Coordinate {
int row;
int col;
public Coordinate(int row, int col) {
this.row = row;
this.col = col;
}
}
public static List<Coordinate> getNeighbors(Coordinate node, int numRows, int numCols) {
int[] deltaRow = {-1, 0, 1, 0}; // Moving UP and DOWN
int[] deltaCol = {0, 1, 0, -1}; // Moving LEFT and RIGHT
List<Coordinate> results = new ArrayList<>(); // Creates empty list of neighbors
// Loop through array of coordinates, 4 directions in this case
for (int i = 0; i < deltaRow.length; i++) {
int newRow = deltaRow[i] + node.row;
int newCol = deltaCol[i] + node.col;
// If new direction does not go out of bounds
if (0 <= newRow && newRow < numRows && 0 <= newCol && newCol < numCols)
results.add(new Coordinate(newRow, newCol)); // Add neighbor to list
}
return results; // Return list of neighbors
}
public static void bfs(List<List<Integer>> dungeonMap, int numRows, int numCols) {
ArrayDeque<Coordinate> queue = new ArrayDeque<>();
// For loop goes through every node on dungeon map, and when it encounters a
// '0' (exit), it adds it to the queue. This initializes our queue.
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
if (dungeonMap.get(i).get(j) == 0)
queue.add(new Coordinate(i, j));
}
}
// Now we have a queue with all of our exits populated. We will proceed with
// going to each exit, checking for neighbors of each exit, and adding updated
// (incremented) neighbor to the queue (after popping exit out).
while (!queue.isEmpty()) {
Coordinate currNode = queue.pop();
// For loop checks each valid neighbor of current node
for (Coordinate neighbor : getNeighbors(currNode, numRows, numCols)) {
// If neighbor is not a max integer (empty space), go to next
// neighbor loop (unless they've all been checked)
if (dungeonMap.get(neighbor.row).get(neighbor.col) != Integer.MAX_VALUE)
continue;
// Else, we set that empty space (neighbor) to the value of our
// current node (currNode) + 1, and add updated neighbor to queue.
dungeonMap.get(neighbor.row).set(neighbor.col, 1 + dungeonMap.get(currNode.row).get(currNode.col));
queue.add(neighbor);
}
}
}
public static List<List<Integer>> mapGateDistances(List<List<Integer>> dungeonMap) {
int numRows = dungeonMap.size();
int numCols = dungeonMap.get(0).size();
bfs(dungeonMap, numRows, numCols); // Calls void function that updates dungeon map
return dungeonMap; // Returns updated dungeon map
}
As we start from the gates, if we encounter an INF value, we will replace it with the gateās value increment, which happens to be 0. Therefore, 0 + 1 = 1. After the replacement, we will add the position of the tile we just updated into the queue. This is because the distance between the gate and any of its neighboring tiles will always be the distance of this tile from the gate plus 1. This is a brilliant approach.
from typing import List
from collections import deque
def map_gate_distances(rooms: List[List[int]]) -> List[List[int]]:
def get_neighbors(coord, value):
overall_rows, overall_cols = len(rooms), len(rooms[0])
r, c = coord
r_coord, c_coord = [-1,0,0,1], [0,1,-1,0]
res = []
for i in range(len(r_coord)):
current_row = r + r_coord[i]
current_col = c + c_coord[i]
if 0 <= current_row < overall_rows and 0 <= current_col < overall_cols:
if rooms[current_row][current_col] != -1 and rooms[current_row][current_col] != 0:
if rooms[current_row][current_col] == 2147483647:
res.append((current_row, current_col))
elif rooms[current_row][current_col] > value:
res.append((current_row, current_col))
return res
def bfs(root):
queue = deque([root])
value = 1
while queue:
N = len(queue)
for _ in range(N):
node = queue.popleft()
for neighbor in get_neighbors(node, value):
r,c = neighbor
rooms[r][c] = value
queue.append(neighbor)
value += 1
for row in range(len(rooms)):
for col in range(len(rooms[0])):
if rooms[row][col] == 0:
room = (row, col)
bfs(room)
return rooms
if __name__ == '__main__':
dungeon_map = [[int(x) for x in input().split()] for _ in range(int(input()))]
res = map_gate_distances(dungeon_map)
for row in res:
print(' '.join(map(str, row)))
from typing import List
from collections import deque
INF = 2**31 - 1
def get_neighbors(x, y, width, height):
offsets = [
(0, 1),
(1, 0),
(0, -1),
(-1, 0)
]
for dx, dy in offsets:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < width and 0 <= new_y < height:
yield new_x, new_y
def map_gate_distances(dungeon_map: List[List[int]]) -> List[List[int]]:
if not dungeon_map or not dungeon_map[0]:
return dungeon_map
queue = deque()
for y in range(len(dungeon_map)):
for x in range(len(dungeon_map[0])):
if dungeon_map[y][x] == 0:
queue.append((x, y, 0))
while queue:
x, y, dist = queue.popleft()
for xi, yi in get_neighbors(x, y, len(dungeon_map[0]), len(dungeon_map)):
if dungeon_map[yi][xi] == INF:
dungeon_map[yi][xi] = dist + 1
queue.append((xi, yi, dist + 1))
return dungeon_map
Ahh its because when an inf is changed to some number of steps its enqueued at the end. This ensures that all gates are processed first. So the closest gate will reach its tile first except when theres a tie between two gates at which point we it doesnāt matter who wins
The solution explanation in the article is really hard to parse since it doesnāt explain why it always generates the distance to the NEAREST gate.
After a bunch of logging to see the order of evaluation, I finally figured out how it works to produce the minimum every timeāstarting from each gate, the neighbors are added for each gate in interleaving sequence, one step of each expanding ring at a time.
Imagine a video of multiple pebbles dropped in a pond. Each frame is evaluated in order. By the time the ripples meet, everything inside each circle has already been processed.
The other āhackā is that you donāt need to keep track of the current distance from each gate, as you might in a DFS, because you just can add one from the node whose neighbors are being evaluated, and you are setting that value before you add it to the queue. Itās counterintuitive since you might be used to evaluating the node itself on each pop(), but in this case youāve already done it and are using it as a jumping off point to process all its neighbors AND to store the previous state from the expanding ring.