Graphs are the most asked topic when it comes to coding interviews. So to help you in your preparation, Ninjas are here to help you. In this article, we will discuss the problem of finding the shortest distance from a guard in a bank.
Problem Statement
We have been given a matrix with the characters "o," "g," and "w," where "o" stands for open area, "g" for ninja guard, and "w" for code studio walls. Change every O in the matrix to the shortest distance away from a guard without being able to pass through any walls. Additionally, in the output matrix, swap out the guards for 0 and the walls for -1.
Example
Input
o
o
o
o
g
o
w
w
o
o
o
o
o
w
o
g
w
w
w
o
o
o
o
o
g
Output
3
3
2
1
0
2
-1
-1
2
1
1
2
3
-1
2
0
-1
-1
-1
1
1
2
2
1
0
Explanation
We can see that for each 'o', the minimum distance a guard is away from it is given in the output matrix.
Now, let's see the proper algorithm and the implementation of the code.
Brute Force Intuition
A simple solution is that we will find all paths from every open gate to every guard and then replace it with the smallest values present. If we talk about the time complexity of this, it would be O(M^2 * N^2).
This is because you will be visiting each node once and from that one node you will be revisiting every other node. After this, you will find the minimum distance out of them. So the total time complexity will be O(M * N)*O(M * N) ~ O(M^2 * N^2).
Let's look at the code for the brute force approach in C++.
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
int x[] = { -1, 0, 1, 0 };
int y[] = { 0, 1, 0, -1 };
// This will check if the current state is valid or not.
bool isvalid(int arr[100][100], int x, int y, int n, int m)
{
// If out of bound.
if (x < n && x >= 0 && y >= 0 && y < m && arr[x][y] != -1)
return true;
else
return false;
}
int dfs(int i, int j, int n, int m, int arr[100][100], vector<vector < bool>> &visited)
{
if (arr[i][j] == 0)
return 0;
if (arr[i][j] == -1 || visited[i][j])
return 1e9;
int minA = 1e9;
visited[i][j] = 1;
for (int p = 0; p < 4; p++)
{
int nx = i + x[p];
int ny = j + y[p];
if (isvalid(arr, nx, ny, n, m))
minA = min(minA, dfs(nx, ny, n, m, arr, visited) + 1);
}
return minA;
}
void GuardinABank(int arr[100][100], int n, int m)
{
vector<vector < int>> dist(n, vector<int> (m, -1));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (arr[i][j] == 1)
{
vector<vector < bool>> visited(n, vector<bool> (m, 0));
// Performing DFS for every 'O'.
dist[i][j] = dfs(i, j, n, m, arr, visited);
}
}
}
// Printing answer.
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (arr[i][j] == 0)
cout << 0 << " ";
else
cout << dist[i][j] << " ";
}
cout << "\n";
}
}
int main()
{
int n = 5;
int m = 5;
// Input Matrix.
char arr1[][5] = {
{
'O', 'O', 'O', 'O', 'G' },
{
'O', 'W', 'W', 'O', 'O' },
{
'O', 'O', 'O', 'W', 'O' },
{
'G', 'W', 'W', 'W', 'O' },
{
'O', 'O', 'O', 'O', 'G' }
};
int arr[100][100];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
char ch = arr1[i][j];
if (ch == 'G')
arr[i][j] = 0;
else if (ch == 'W')
arr[i][j] = -1;
else if (ch == 'O')
arr[i][j] = 1;
}
GuardinABank(arr, n, m);
}
Output
3
3
2
1
0
2
-1
-1
2
1
1
2
3
-1
2
0
-1
-1
-1
1
1
2
2
1
0
This method will result in TLE. Thus, we should think of a better approach.
BFS Approach
BFS (Breadth First Search) is used to find the minimum path between two points when the edge weight is 1. The plan here is to do a BFS.
We first enqueue all of the guard cells, then loop until the queue is not empty.
The front cell is removed from the queue for each loop iteration, and for each of its four surrounding cells, if the cell is in an open area and the guard's distance has not yet been determined, we update that distance and re-enqueue the cell.
We print the distance matrix following the BFS method's completion.
Let's now see the implementation of this algorithm.
C++ Code
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
/* This will check if the current state is valid or not. */
bool isvalid(int arr[100][100], int x, int y, int n, int m)
{
/* If out of bound. */
if (x < n && x >= 0 && y >= 0 && y < m && arr[x][y] != -1)
return true;
else
return false;
}
void GuardinABank(int arr[100][100], int n, int m)
{
int x[] = { -1, 0, 1, 0 };
int y[] = { 0, 1, 0, -1 };
int dist[n][m];
/* Queue for performing BFS. */
queue<pair<int, int>> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (arr[i][j] == 0)
{
q.push(mk(i, j));
dist[i][j] = 0;
}
else if (arr[i][j] == -1)
dist[i][j] = -1;
else
dist[i][j] = INT_MAX;
}
/* Performing BFS. */
while (!q.empty())
{
int x1 = q.front().first;
int y1 = q.front().second;
for (int i = 0; i < 4; i++)
{
int x2 = x1 + x[i];
int y2 = y1 + y[i];
if (isvalid(arr, x2, y2, n, m) && dist[x2][y2] > dist[x1][y1] + 1)
{
dist[x2][y2] = dist[x1][y1] + 1;
q.push(mk(x2, y2));
}
}
q.pop();
}
/* Printing answer. */
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cout << dist[i][j] << " ";
cout << "\n";
}
}
int main()
{
int n = 5;
int m = 5;
/* Input Matrix. */
char arr1[][5] = {
{ 'O', 'O', 'O', 'O', 'G' },
{ 'O', 'W', 'W', 'O', 'O' },
{ 'O', 'O', 'O', 'W', 'O' },
{ 'G', 'W', 'W', 'W', 'O' },
{ 'O', 'O', 'O', 'O', 'G' }
};
int arr[100][100];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
char ch = arr1[i][j];
if (ch == 'G')
arr[i][j] = 0;
else if (ch == 'W')
arr[i][j] = -1;
else if (ch == 'O')
arr[i][j] = 1;
}
GuardinABank(arr, n, m);
}
Python Code
from collections import deque
''' Function for checking if a state is safe or not. '''
def issafe(n,x,y):
if x<0 or x>=n or y<0 or y>=n:
return 0
return 1
''' If a state is open, then return true. '''
def isvalid(g,x,y):
if g[x][y]=="o":
return 1
return 0
def shortestdistanceofguard(g,n):
row=[-1,0,1,0]
col=[0,1,0,-1]
''' Queue for BFS. '''
q=deque()
output=[[-1 for _ in range(n)] for _ in range(n)]
''' Insert all 'g' cells. '''
for i in range(n):
for j in range(n):
if g[i][j]=="g":
output[i][j]=0
q.append([i,j,0])
''' Performing BFS. '''
while len(q):
p=q.popleft()
for i in range(4):
if issafe(n,p[0]+row[i],p[1]+col[i]) and isvalid(g,p[0]+row[i],p[1]+col[i]) and output[p[0]+row[i]][p[1]+col[i]]==-1:
output[row[i]+p[0]][p[1]+col[i]]=p[2]+1
q.append([row[i]+p[0],col[i]+p[1],p[2]+1])
return output
''' Input. '''
g=[["o" ,"o","o","o","g"],
["o","w","w","o","o"],
["o","o","o","w","o"],
["g","w","w","w","o"],
["o","o","o","o","g"]]
print(shortestdistanceofguard(g,5))
Output
3
3
2
1
0
2
-1
-1
2
1
1
2
3
-1
2
0
-1
-1
-1
1
1
2
2
1
0
Complexities
Time complexity
O(M * N), where M and N denote the number of rows and columns in the graph.
Reason: We are performing a BFS on the graphs; thus, we will traverse all the elements once; as we know, there are a total of M * N elements. Thus the time complexity is O(M * N).
Space complexity
O(M * N), where M and N denote the number of rows and columns in the graph.
Reason: This is the space taken by the queue for performing BFS.
Frequently Asked Questions
What memory representation does a graph have?
A graph can be kept in memory in three ways:
Edges act as pointers, and nodes as objects.
A matrix that includes each edge weight that connects nodes x and y.
Edges between numbered nodes listed.
What do you mean by the depth of a vertex?
The number of branches that lead from a root to a vertex determines the vertex's depth. Therefore, the root's depth is zero. The number of the vertex in the path from the root to the vertex determines the vertex's level.
Does Depth-First Search identify the shortest route?
One of the primary graph algorithms is Depth-First Search. Depth-First Search locates the lexicographical first path from each source vertex to each vertex in the graph. Since there is only one simple path in a tree, Depth-First Search will also locate the shortest paths across the tree, but this is not the case for generic graphs.
What technique is employed to depict a graph in relation?
The adjacency matrix is used to achieve this type of representation. The adjacency matrix shows which nodes are close on a graph or whether an edge connects two nodes.
How come Breath-First Search is quicker than DFS?
Breath-First Search should usually be quicker if the searched element is typically higher in the search tree because it travels level by level and can be stopped when a matched element is discovered. If the searched element is usually rather deep and locating one among many is adequate, DFS might be faster.
Conclusion
In the article, we have discussed one popular question: Find Shortest Distance from a Guard in a Bank. We hope that this article helped you understand the concept of graphs, and if you want to learn more about graphs, check out our other blogs on graphs:
305+ registered