Solution For Walls And Gates

Problem statement:

You are given a m x n 2D grid initialized with these three possible values.

• -1 – A wall or an obstacle.
• 0 – A gate.
• INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example:

Input: [[INF, -1, 0, INF],
[INF, INF, INF, -1],
[INF, -1, INF, -1],
[ 0, -1, INF, INF]]

Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Solution:

The problem is asking us to find the minimum distance from each empty room (INF) to the nearest gate (0). We can solve this problem by using a variation of Breadth-first search (BFS). Here’s how we can do it:

1. First, we need to find all the gates (0s) in the grid. We can do this by iterating through the entire grid and adding the gates to a queue.
2. Next, we will perform a BFS on each gate in the queue until we have visited every empty room (INF) in the grid. We can use a distance variable to keep track of the minimum distance from the gates to other rooms.
3. We start by processing the first gate in the queue. We will create a new row and column variable that is used to keep track of the neighboring cells. We will check the four neighbor cells (up, down, left, right) of the current cell to see if they are empty and have not been visited yet.
4. If a neighbor cell is empty and has not been visited, we can update its value to be the current distance + 1. We then add this neighbor cell to the queue.
5. We repeat steps 3-4 for every other cell in the queue until all the empty cells have been visited.
6. We can then return the updated grid.

Here’s the implementation of the above algorithm in Python:

“`
from collections import deque

class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
“””
Do not return anything, modify rooms in-place instead.
“””
#helper function to check if the cell is empty
def is_empty(row, col):
return 0 <= row < m and 0 <= col < n and rooms[row][col] == INF

``````    #the directions to move
dirs = [[1,0], [-1,0], [0,1], [0,-1]]

#constants
INF = 2 ** 31 - 1
GATE = 0

#get the dimensions of the input matrix
m = len(rooms)
n = len(rooms[0])

#initialize a double ended queue
queue = deque()

#add all gates to the queue
for i in range(m):
for j in range(n):
if rooms[i][j] == GATE:
queue.append((i,j))

#start processing gates until we have visited all the empty rooms
while queue:
row, col = queue.popleft()
distance = rooms[row][col] + 1
for i, j in dirs:
new_row = row + i
new_col = col + j
if is_empty(new_row, new_col):
rooms[new_row][new_col] = distance
queue.append((new_row, new_col))
``````

“`

The time complexity of the above algorithm is O(mn) where m and n are the dimensions of the input matrix. The space complexity is O(mn) as well since we are storing the gates in a double-ended queue.

Step by Step Implementation For Walls And Gates

```You can use the following class to represent a cell in the 2D grid:

class Cell {
public int row;
public int col;
public Cell(int row, int col) {
this.row = row;
this.col = col;
}
}

class Solution {
public void wallsAndGates(int[][] grid) {
// TODO: Implement your solution here
}
}```
```You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
0  -1 INF INF
After running your function, the 2D grid should be:
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4```
```You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
0  -1 INF INF
After running your function, the 2D grid should be:
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4```
```You are given a m x n 2D grid initialized with these three possible values.

-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
0  -1 INF INF
After running your function, the 2D grid should be:
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4```
```You can use BFS or DFS to find the shortest path from each empty cell to a gate. The time complexity is O(mn) where m is the number of rows and n is the number of columns.

Here is the code in C#:

public class Solution {
public void WallsAndGates(int[][] rooms) {
if (rooms.Length == 0 || rooms[0].Length == 0) return;
int m = rooms.Length, n = rooms[0].Length;
Queue queue = new Queue();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 0) {
queue.Enqueue(new int[] {i, j});
}
}
}
int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (queue.Count > 0) {
int[] curr = queue.Dequeue();
int row = curr[0], col = curr[1];
foreach (int[] dir in dirs) {
int r = row + dir[0], c = col + dir[1];
if (r < 0 || r >= m || c < 0 || c >= n || rooms[r][c] < rooms[row][col] + 1) continue;
rooms[r][c] = rooms[row][col] + 1;
queue.Enqueue(new int[] {r, c});
}
}
}
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]