Walls and Gates / Zombie in Matrix - Graph / Matrix as Graph

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.

the solution is using multi-source bfs

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!!

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.ArrayDeque;

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
}
1 Like

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.

My Solution using the BFS tempalte

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

Example is Go

func mapGateDistances(dungeonMap [][]int) [][]int {
	queue := [][]int{}
	deltaRow := []int{-1, 0, 1, 0}
	deltaCol := []int{0, -1, 0, 1}

	for i := range dungeonMap {
		for j := range dungeonMap[i] {
			if dungeonMap[i][j] == 0 {
				queue = append(queue, []int{i, j})
			}
		}
	}

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for i := range deltaRow {
			nr := cur[0] + deltaRow[i]
			nc := cur[1] + deltaCol[i]

			if nr < 0 || nc < 0 || nr >= len(dungeonMap) || nc >= len(dungeonMap[0]) || dungeonMap[nr][nc] == 0 || dungeonMap[nr][nc] < dungeonMap[cur[0]][cur[1]]+1 {
				continue
			}
			dungeonMap[nr][nc] = dungeonMap[cur[0]][cur[1]] + 1
			queue = append(queue, []int{nr, nc})
		}
	}
	return dungeonMap
}

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.