There are many algorithms to solve questions related to graphs, a data structure that consists of nodes and edges. For example, to find the shortest path from a given node we can use algorithms like Dijkstra Algorithm, Breadth First Search, etc. This article will discuss a similar graph question, known as the Wall and Gates problem. For this question, you should have prior knowledge of BFS.
What is the Walls and Gates problem?
In the Walls and Gates problem, you are given a matrix or 2-D array in which values can either be:
- 0, which represents the door,
- -1, which represents the wall,
- INF, infinity which represents an empty room.
You have to fill all the INF values to a number that represents the minimum distance between that room and any door. You can not walk through walls. So in case we cannot reach any door the value remains INF for that cell. Let’s understand this with an example.
In the above matrix, the 1st cell i.e. (0,0) value will be replaced with value 4 as the minimum distance of any gate from this cell is 4. As shown here.
The matrix will look like this after putting all values.
The naive solution is to go to each cell and check what is the minimum distance of the gate from that cell. If no such path exists return -1. For checking minimum distance we can use DFS or BFS.
Let’s understand this step by step:
- Iterate two loops that go to each cell.
- If the cell value is INF, go to adjacent cells by incrementing a count value till it reaches a cell whose value is 0. If it encounters -1 do not move further in that direction.
- Now replace the value of the cell with the count value.
The time complexity of the above code is O((nm)^2). We are first going to each cell in a matrix whose time complexity is O(nm). After that, we found a minimum distance for this cell which again required O(nm). So, the overall time complexity will be O((nm)^2). The space complexity will remain O(1). As no extra space is needed.
Optimized BFS Approach
In the above approach to solving the Walls and Gates problem, we are using O((nm)^2) time complexity because we are first going to each cell, and then from that cell, we are checking the minimum distance. This can be reduced if we do the reverse approach.
We should start from each gate and then go to each adjacent cell if the cell value is INF and update the value from the previous value + 1. This problem is the same as BFS where we used to find the shortest distance from a cell. The only difference is that here we are pushing more than one initial value.
Let’s examine this approach:
- First, create a queue that stores a pair of pairs whose first value is the current value, second represents the number of rows, and third represents the number of columns.
- Push all the indexes into the queue which are gates with value 0.
- Iterate over this queue till it becomes empty.
- Create a sz variable that stores the size of the current element.
- Run a loop of size ‘sz’ and remove the top element from the queue. Take the value of this element as a current value. Now go to every adjacent cell if the current value + 1 is smaller than their initial value. Now push this value (current value + 1 ) and index into the queue.
- Update the value of the cell with the current value + 1.
- Return the matrix once all the loops are done.
Let us now move to code it.
C++ Code
Here is the C++ program to solve the Walls and Gates problem:
#include <bits/stdc++.h>
using namespace std;
// directions in which one can move i.e. up, down, left, and right.
vector<pair<int,int>>mov = {{1,0}, {-1,0}, {0,1}, {0,-1}};
bool is_valid(int x, int y, int n, int m){
return (x>=0 && y>=0 && x<n && y<m);
}
int main(){
vector<vector<int>>grid = {{INT_MAX, 0, INT_MAX}, {INT_MAX, INT_MAX, -1}, {0, -1, INT_MAX }};
int n = grid.size(), m = grid[0].size();
queue<pair<int,pair<int,int>>>q;
// inserting all the gates into the queue
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j]==0){
q.push({0,{i,j}});
}
}
}
// BFS
while(q.size()){
int sz = q.size();
while(sz--){
auto p = q.front();
q.pop();
int count = p.first, x = p.second.first, y = p.second.second;
for(auto cc:mov){
int x1 = cc.first, y1 = cc.second;
int a = x + x1, b = y + y1;
// checking if a,b are valid index or not
if(!is_valid(a,b,n,m) || grid[a][b] <= (count+1)) continue;
grid[a][b] = count+1;
q.push({count+1, {a, b}});
}
}
}
// printing all the values of the matrix
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cout<<grid[i][j]<<" ";
}
cout<<endl;
}
return 0;
}Java Code
Here is the Java program for the solution:
import java.util.*;
public class Main {
// directions in which one can move i.e. up, down, left, and right.
static int[][] mov = {{1,0}, {-1,0}, {0,1}, {0,-1}};
static boolean isValid(int x, int y, int n, int m){
return (x>=0 && y>=0 && x<n && y<m);
}
public static void main(String[] args) {
int[][] grid = {{Integer.MAX_VALUE, 0, Integer.MAX_VALUE},
{Integer.MAX_VALUE, Integer.MAX_VALUE, -1},
{0, -1, Integer.MAX_VALUE}};
int n = grid.length, m = grid[0].length;
Queue<int[]> q = new LinkedList<>();
// inserting all the gates into the queue
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 0){
q.add(new int[]{0, i, j});
}
}
}
// BFS
while(!q.isEmpty()){
int sz = q.size();
while(sz-- > 0){
int[] p = q.poll();
int count = p[0], x = p[1], y = p[2];
for(int[] cc : mov){
int x1 = cc[0], y1 = cc[1];
int a = x + x1, b = y + y1;
// checking if a,b are valid index or not
if(!isValid(a,b,n,m) || grid[a][b] <= (count+1)) continue;
grid[a][b] = count+1;
q.add(new int[]{count+1, a, b});
}
}
}
// printing all the values of the matrix
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
System.out.print(grid[i][j] + " ");
}
System.out.println();
}
}
}Python Code
You can do it in Python also to crack the Walls and Gates:
from collections import deque
import sys
# directions in which one can move i.e. up, down, left and right.
mov = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def isValid(x, y, n, m):
return (0 <= x < n) and (0 <= y < m)
if __name__ == "__main__":
grid = [[sys.maxsize, 0, sys.maxsize],
[sys.maxsize, sys.maxsize, -1],
[0, -1, sys.maxsize]]
n, m = len(grid), len(grid[0])
q = deque()
# inserting all the gates into the queue
for i in range(n):
for j in range(m):
if grid[i][j] == 0:
q.append((0, i, j))
# BFS
while q:
sz = len(q)
while sz > 0:
p = q.popleft()
count, x, y = p
for cc in mov:
x1, y1 = cc
a, b = x + x1, y + y1
# checking if a, b are valid index or not
if not isValid(a, b, n, m) or grid[a][b] <= (count + 1):
continue
grid[a][b] = count + 1
q.append((count + 1, a, b))
sz -= 1
# printing all the values of the matrix
for i in range(n):
for j in range(m):
print(grid[i][j], end=" ")
print()Output:
1 0 1
1 1 -1
0 -1 INF
Time complexity will be reduced to O(nm) for the Walls and Gates problem using BFS. We are doing BFS traversal only whose time complexity is O(N) where N is the number of traversals. Space complexity will be O(nm). As maximum n*m gates can be possible.
Here is a comparison of both the approaches:
| Approach | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Brute Force | O( (nm)^2) | O(1) | We are going to each cell and from each cell we are calculating the minimum distance. |
| Optimized Approach | O( nm ) | O(nm) | In this approach, we are using BFS, which traverses the matrix only once. |
Conclusion
This article shows how can we find the shortest distance optimally through the BFS algorithm to solve the Walls and Gates problem. The BFS algorithm has a lot more applications. One can learn by solving some more questions based on BFS like Minimum Path Sum, Cherry Pickup, etc.
