Given a 2-D matrix of characters of size n*m, where H – Represents a house, W – Represents a well, O – Represents an open ground, and N – Prohibited area(Not allowed to enter in this area). Every house in the village needs to take the water from the well, as the family members are so busy with their work, so every family wants to take the water from the well in minimum time, which is possible only if they have to cover as less distance as possible. Your task is to determine the minimum distance that a person in the house should travel to take out the water and carry it back to the house. A person is allowed to move only in four directions left, right, up, and down. That means if he/she is the cell (i, j), then the possible cells he/she can reach in one move are (i, j – 1), (i, j + 1), (i – 1, j), (i + 1, j), and the person is not allowed to move out of the grid. Note: For all the cells containing ‘N’, ‘ W’, and ‘O’ our answer should be 0, and for all the houses where there is no possibility of taking water our answer should be -1.
Examples:
Input: n = 3, m = 3, c[][]: {H, H, H}, {H, W, H}, {H, H, H}
Output:
4 2 4
2 0 2
4 2 4
Explanation: There is only one well hence all the houses present in the corner of the matrix will have to travel a minimum distance of 4, 2 are for a house to well, and the other two is for a well to the house. And the rest of the houses have to travel a minimum distance of 2 (House -> Well -> House).Input: n = 5, m = 5, c[][]: {H, N, H, H, H}, {N, N, H, H, W}, {W, H, H, H, H}, {H, H, H, H, H}, {H, H, H, H, H}
Output:
-1 0 6 4 2
0 0 4 2 0
0 2 4 4 2
2 4 6 6 4
4 6 8 8 6
Explanation: There is no way any person from the house in cell (0, 0) can take the water from any well, and for the rest of the houses, there is the same type of strategy we have to follow as followed in example 1.
Approach: To solve the problem follow the below idea:
The approach used is Breadth First Search (BFS) algorithm to find the minimum distance from each cell to the nearest well.
Below are the steps involved in the implementation of the code:
- Initialize a 2D array ‘ans‘ of size n x m, which will store the minimum distance from each cell to the nearest well. Initialize all values in ‘ans’ to Integer.MAX_VALUE using Arrays.fill() method.
- Initialize a boolean 2D array ‘v’ of size n x m, which will store whether a cell has been visited or not.
- Initialize a queue ‘q’ to store the cells that are being processed.
- Traverse the entire matrix ‘c’, and add all wells to the queue ‘q’. Mark the corresponding cell as visited in the boolean array ‘v’ and set the distance of the cell in the ‘ans’ array to 0.
- Define two arrays ‘dx’ and ‘dy‘ to represent the possible movements in x and y directions respectively, i.e., left, right, up, and down.
- While the queue ‘q’ is not empty, pop the first cell from the queue, and for each of its neighboring cells, check if the cell has not been visited before, is within the boundaries of the matrix, and is not a blocked cell (‘N’). If these conditions are satisfied, set the distance of the neighboring cell in the ‘ans‘ array to the current cell’s distance + 1, mark the neighboring cell as visited, and add it to the queue ‘q’.
- Traverse the entire matrix ‘c’ again, and for each cell, if it is either blocked or already a well, set its distance in the ‘ans‘ array to 0. If the distance in the ‘ans‘ array is still Integer.MAX_VALUE, set the distance to -1 to indicate that there is no path to a well. Otherwise, multiply the distance by 2, since the problem requires the distance to be in terms of the time taken by the Chef to reach the well.
- Return the ‘ans‘ array.
Below is the code implementation of the above code:
C++
// C++ code for the baove approach: #include <climits> #include <iostream> #include <queue> #include <vector> using namespace std; // Structure of data type struct Pair { int a, b, c; Pair( int a, int b, int c) { this ->a = a; this ->b = b; this ->c = c; } }; // Function to check minimum time required to take water // from the well vector<vector< int > > chefAndWells( int n, int m, vector<vector< char > >& c) { // Create a 2D matrix vector<vector< int > > ans(n, vector< int >(m, INT_MAX)); vector<vector< bool > > v(n, vector< bool >(m, false )); queue<Pair> q; for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (c[i][j] == 'W' ) { v[i][j] = true ; ans[i][j] = 0; q.push(Pair(i, j, 0)); } } } int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 }; // BFS to find minimum time while (!q.empty()) { Pair p = q.front(); q.pop(); for ( int i = 0; i < 4; i++) { int nx = p.a + dx[i]; int ny = p.b + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !v[nx][ny] && c[nx][ny] != 'N' ) { q.push(Pair(nx, ny, p.c + 1)); v[nx][ny] = true ; ans[nx][ny] = p.c + 1; } } } // Iterate over matrix to get the final result for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (c[i][j] == '.' || c[i][j] == 'N' ) { ans[i][j] = 0; } else if (ans[i][j] == INT_MAX) { ans[i][j] = -1; } else { ans[i][j] *= 2; } } } return ans; } // Driver code int main() { int n = 3; int m = 3; vector<vector< char > > c = { { 'H' , 'H' , 'H' }, { 'H' , 'W' , 'H' }, { 'H' , 'H' , 'H' } }; // Function call vector<vector< int > > ans = chefAndWells(n, m, c); // Print the result for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { cout << ans[i][j] << " " ; } cout << endl; } return 0; } // This code is contributed by akshitaguprzj3 |
Java
// Java code for the baove approach: import java.util.*; public class Solution { // Function to check minimum time // Required to take water from well public static int [][] chefAndWells( int n, int m, char [][] c) { // Create a 2D matrix int [][] ans = new int [n][m]; for ( int i = 0 ; i < n; i++) { Arrays.fill(ans[i], Integer.MAX_VALUE); } boolean [][] v = new boolean [n][m]; Queue<Pair> q = new LinkedList<>(); for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { if (c[i][j] == 'W' ) { v[i][j] = true ; ans[i][j] = 0 ; q.add( new Pair(i, j, 0 )); } } } int [] dx = { 0 , 0 , - 1 , 1 }; int [] dy = { - 1 , 1 , 0 , 0 }; // BFS to find minimum time while (!q.isEmpty()) { Pair p = q.poll(); for ( int i = 0 ; i < 4 ; i++) { int nx = p.a + dx[i]; int ny = p.b + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !v[nx][ny] && c[nx][ny] != 'N' ) { q.add( new Pair(nx, ny, p.c + 1 )); v[nx][ny] = true ; ans[nx][ny] = p.c + 1 ; } } } // Iterate over matrix to // get the final result for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { if (c[i][j] == '.' ) { ans[i][j] = 0 ; } else if (c[i][j] == 'N' ) { ans[i][j] = 0 ; } else if (ans[i][j] == Integer.MAX_VALUE) { ans[i][j] = - 1 ; } else { ans[i][j] *= 2 ; } } } return ans; } // Structure of data type public static class Pair { int a, b, c; public Pair( int a, int b, int c) { this .a = a; this .b = b; this .c = c; } } // Driver code public static void main(String[] args) { int n = 3 ; int m = 3 ; char [][] c = { { 'H' , 'H' , 'H' }, { 'H' , 'W' , 'H' }, { 'H' , 'H' , 'H' } }; // Function call int [][] ans = chefAndWells(n, m, c); // Print the result for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { System.out.print(ans[i][j] + " " ); } System.out.println(); } } } |
Python3
# Python3 code for the baove approach: from collections import deque # Structure of data type class Pair: def __init__( self , a, b, c): self .a = a self .b = b self .c = c # Function to check minimum time required to take water # from the well def chefAndWells(n, m, c): # Create a 2D matrix ans = [[ float ( 'inf' )] * m for _ in range (n)] v = [[ False ] * m for _ in range (n)] q = deque() for i in range (n): for j in range (m): if c[i][j] = = 'W' : v[i][j] = True ans[i][j] = 0 q.append(Pair(i, j, 0 )) dx = [ 0 , 0 , - 1 , 1 ] dy = [ - 1 , 1 , 0 , 0 ] # BFS to find minimum time while q: p = q.popleft() for i in range ( 4 ): nx = p.a + dx[i] ny = p.b + dy[i] if 0 < = nx < n and 0 < = ny < m and not v[nx][ny] and c[nx][ny] ! = 'N' : q.append(Pair(nx, ny, p.c + 1 )) v[nx][ny] = True ans[nx][ny] = p.c + 1 # Iterate over matrix to get the final result for i in range (n): for j in range (m): if c[i][j] = = '.' or c[i][j] = = 'N' : ans[i][j] = 0 elif ans[i][j] = = float ( 'inf' ): ans[i][j] = - 1 else : ans[i][j] * = 2 return ans # Driver code n = 3 m = 3 c = [[ 'H' , 'H' , 'H' ], [ 'H' , 'W' , 'H' ], [ 'H' , 'H' , 'H' ]] # Function call ans = chefAndWells(n, m, c) # Print the result for i in range (n): for j in range (m): print (ans[i][j], end = " " ) print () # This code is contributed by akshitaguprzj3 |
C#
// C# code for the baove approach using System; using System.Collections.Generic; public class Pair { public int a, b, c; public Pair( int a, int b, int c) { this .a = a; this .b = b; this .c = c; } } public class Program { // Function to check minimum time required to take water // from the well public static List<List< int > > ChefAndWells( int n, int m, List<List< char > > c) { // Create a 2D matrix to store the result List<List< int > > ans = new List<List< int > >(); for ( int i = 0; i < n; i++) { ans.Add( new List< int >()); for ( int j = 0; j < m; j++) { ans[i].Add( int .MaxValue); } } // Create a matrix to track visited locations List<List< bool > > v = new List<List< bool > >(); for ( int i = 0; i < n; i++) { v.Add( new List< bool >()); for ( int j = 0; j < m; j++) { v[i].Add( false ); } } // Create a queue for BFS traversal Queue<Pair> q = new Queue<Pair>(); // Initialize the queue with 'W' locations for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (c[i][j] == 'W' ) { v[i][j] = true ; ans[i][j] = 0; q.Enqueue( new Pair(i, j, 0)); } } } // Define directional vectors for BFS int [] dx = { 0, 0, -1, 1 }; int [] dy = { -1, 1, 0, 0 }; // BFS to find minimum time while (q.Count > 0) { Pair p = q.Dequeue(); for ( int i = 0; i < 4; i++) { int nx = p.a + dx[i]; int ny = p.b + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !v[nx][ny] && c[nx][ny] != 'N' ) { q.Enqueue( new Pair(nx, ny, p.c + 1)); v[nx][ny] = true ; ans[nx][ny] = p.c + 1; } } } // Iterate over the matrix to adjust the final // result for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { if (c[i][j] == '.' || c[i][j] == 'N' ) { ans[i][j] = 0; } else if (ans[i][j] == int .MaxValue) { ans[i][j] = -1; } else { ans[i][j] *= 2; } } } return ans; } public static void Main( string [] args) { int n = 3; int m = 3; List<List< char > > c = new List<List< char > >() { new List< char >{ 'H' , 'H' , 'H' }, new List< char >{ 'H' , 'W' , 'H' }, new List< char > { 'H' , 'H' , 'H' } }; // Function call List<List< int > > ans = ChefAndWells(n, m, c); // Print the result for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { Console.Write(ans[i][j] + " " ); } Console.WriteLine(); } } } // This code is contributed by Susobhan Akhuli |
Javascript
<script> // JavaScript code for the baove approach // Structure of data type class Pair { constructor(a, b, c) { this .a = a; this .b = b; this .c = c; } } // Function to check minimum time required to take water from the well function chefAndWells(n, m, c) { // Create a 2D matrix const ans = new Array(n).fill( null ).map(() => new Array(m).fill(Number.MAX_SAFE_INTEGER)); const v = new Array(n).fill( null ).map(() => new Array(m).fill( false )); const dx = [0, 0, -1, 1]; const dy = [-1, 1, 0, 0]; const q = []; for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (c[i][j] === 'W' ) { v[i][j] = true ; ans[i][j] = 0; q.push( new Pair(i, j, 0)); } } } // BFS to find minimum time while (q.length > 0) { const p = q.shift(); for (let i = 0; i < 4; i++) { const nx = p.a + dx[i]; const ny = p.b + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && !v[nx][ny] && c[nx][ny] !== 'N' ) { q.push( new Pair(nx, ny, p.c + 1)); v[nx][ny] = true ; ans[nx][ny] = p.c + 1; } } } // Iterate over matrix to get the final result for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (c[i][j] === '.' || c[i][j] === 'N' ) { ans[i][j] = 0; } else if (ans[i][j] === Number.MAX_SAFE_INTEGER) { ans[i][j] = -1; } else { ans[i][j] *= 2; } } } return ans; } const n = 3; const m = 3; const c = [ [ 'H' , 'H' , 'H' ], [ 'H' , 'W' , 'H' ], [ 'H' , 'H' , 'H' ] ]; // Function call const ans = chefAndWells(n, m, c); // Print the result for (let i = 0; i < n; i++) { document.write(ans[i].join( ' ' )+ "<br>" ); } // This code is contributed by Susobhan Akhuli </script> |
4 2 4 2 0 2 4 2 4
Time Complexity: O(n*m)
Auxiliary Space O(n*m)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!