Shortest Distance from All Buildings

Problem Statement

Given a 2D grid g of size n x n, where each cell can either contain a 1 (indicating a starting point) or a 0 (indicating an empty space), your task is to calculate the shortest distance from each cell to the nearest cell containing a 1. The distance between two adjacent cells is considered to be 1. You need to return a 2D grid dis of the same size, where dis[i][j] represents the shortest distance from the cell (i, j) to the nearest 1 in the original grid.

Explanation of the Code

This Python code accomplishes the task using Breadth-First Search (BFS). Here’s a step-by-step explanation:

1. Function Definition: get_distances(g, vis)

• Parameters:

  • g: The input 2D grid representing the initial layout of 1s and 0s.
  • vis: A 2D grid of the same size, initialized to 0s, used to keep track of visited cells during the BFS.

• Returns:

  • A 2D grid dis where dis[i][j] holds the shortest distance from the cell (i, j) to the nearest 1 in the grid g.

2. Initialization

• n: The size of the grid (assuming g is a square grid).
• dis: A 2D grid initialized with very large values (n*n), representing initial distances that will be minimized later.
• q: A queue used for BFS traversal.
• delta_arr: A list of tuples representing the four possible directions of movement (up, down, left, right).

3. Identify All Starting Points (Cells with 1)

• The code first traverses the entire grid g.
• For every cell containing 1, it marks that cell as visited in vis and adds the cell coordinates (i, j) along with the initial distance 0 to the queue q.

4. BFS Traversal to Calculate Distances

• The BFS loop runs as long as there are cells in the queue q.
• For each cell (i, j) dequeued, the distance d is assigned to dis[i][j].
• The loop then considers all four possible neighboring cells (new_row, new_col).
• If a neighboring cell has not been visited (i.e., vis[new_row][new_col] == 0), it is marked as visited and added to the queue with an incremented distance d + 1.

5. Return the Distance Grid

• After BFS completes, the grid dis containing the shortest distances is returned.

6. Main Function

• The main() function initializes a sample grid g and a corresponding vis grid.
• It then calls the get_distances function to compute the distances and prints both the original grid g and the computed distance grid dis.

7. Output Example

For the input grid g = [[1, 0, 1], [1, 1, 0], [1, 0, 0]], the output dis will be:

g = [[1, 0, 1], [1, 1, 0], [1, 0, 0]]
dis = [[0, 1, 0], [0, 0, 1], [0, 1, 2]]

This indicates that each cell in dis contains the shortest distance to the nearest 1 in the original grid g.

def get_distances(g, vis):
    n = len(g)
    dis = [[n*n for _ in range(n)] for _ in range(n)]
    q = []
    delta_arr = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    # [init] traverse through the graph and identify every 1
    for i in range(n):
        for j in range(n):
            ele = g[i][j]
            if ele == 1:
                vis[i][j] = 1
                q.append((i, j, 0))
        

    # get the other distances using BFS
    while q:
        i, j, d = q.pop(0)
        dis[i][j] = d
        
        for delta in delta_arr:
            new_row = i + delta[0]
            new_col = j + delta[1]
           
            if -1 < new_col < n and -1 < new_row < n and vis[new_row][new_col] == 0:
                vis[new_row][new_col] = 1
                q.append((new_row, new_col, d + 1))
    
    return dis


def main():
    g = [[1, 0, 1], [1, 1, 0], [1, 0, 0]]
    n = len(g)
    vis = [[0 for _ in range(n)] for _ in range(n) ]
    dis = get_distances(g, vis)
    print("g =", g)
    print("dis =", dis)


if __name__ == "__main__":
    main()

Step-by-Step Code Breakdown

1. Initialization:

   • Define the grid size n.
   • Create the dis grid initialized to n*n.
   • Initialize an empty queue q and define the possible movement directions in delta_arr.

2. Identify All 1s in the Grid:

   • Traverse the grid g.
   • For each 1, mark the corresponding cell in vis as visited and add it to the queue with distance 0.

3. BFS to Calculate Distances:

   • While there are items in the queue:
     • Dequeue the first item and update its corresponding distance in dis.
     • For each of the four possible directions, calculate the new position.
     • If the new position is valid and not visited, mark it as visited, update its distance, and enqueue it.

4. Output:

   • Return the dis grid as the result.
   • The main() function demonstrates how to use this function with an example grid.