Minimizing water collection distance in Geek’s village

By Ann Roberts On May 14, 2023

Geek’s village is represented by a 2-D matrix of characters of size n*m, where

H – Represents a house
W – Represents a well
. – Represents an open ground
N – Prohibited area(Not allowed to enter 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 ‘.’ 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 is for house to well and other two is for well to 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 idea to use BFS to traverse the village and calculate the distances from the well to each house.The BFS algorithm can be used to traverse this graph starting from the well, and it will visit all the cells reachable from the well in increasing order of their distance from the well.

By maintaining a distance array, where the distance of each cell is initialized to a large value, and updating the distance of each cell whenever a shorter path is found, we can find the minimum distance from the well to each house.

The BFS algorithm ensures that we explore all the reachable cells in a systematic manner, guaranteeing that we find the shortest path to each house.

Follow the steps to solve the problem:

Create an empty queue q and a boolean matrix v of size n x m to keep track of the visited cells. Also, create an integer matrix ans of size n x m to store the minimum distance from the well to each cell.
Initialize all the elements of ans to Integer. MAX_VALUE and all the elements of v to false.
Iterate through the 2D matrix c and find the cell containing the well. Mark this cell as visited in v, set its distance in ans to 0, and add it to the queue q as a pair object containing its row, column, and distance.
Define two arrays dx and dy containing the horizontal and vertical directions of movement, respectively, as {-1, 0, 1, 0} and {0, 1, 0, -1}.
While the queue q is not empty, remove the first element from the queue as a pair object p.
For each of the four directions of movement, calculate the row and column of the neighbor cell using nx = p.a + dx[i] and ny = p.b + dy[i], where i is the index of the current direction.
Check if the neighbor cell is inside the grid (i.e., nx ≥ 0 && nx < n && ny ≥ 0 && ny < m), not already visited (i.e., !v[nx][ny]), and not a prohibited cell (i.e., c[nx][ny] != ‘N’).
If the above conditions are met, mark the neighbor cell as visited in v, set its distance in ans to p.c + 1, and add it to the end of the queue q as a pair object containing its row, column, and distance (q.add(new pair(nx, ny, p.c + 1))).
After the BFS traversal is complete, iterate through the ans matrix again and update the distance of each cell as follows:
- If the cell contains an obstacle (i.e., c[i][j] == ‘N’), set its distance to 0.
- If the cell is open ground or the well (i.e., c[i][j] == ‘.’ || c[i][j] == ‘W’), set its distance to 0.
- If the cell was not reachable from the well, set its distance to -1.
- Otherwise, double the distance of the cell (i.e., ans[i][j] *= 2).
Return the ans matrix as the output.

Below is the implementation for the above approach:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > chefAndWells(int n, int m,
                                  vector<vector<char> >& c)
{
    vector<vector<int> > res(n, vector<int>(m, 1e9));
    queue<pair<int, int> > q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == 'W') {
                q.push({ i, j });
                res[i][j] = 0;
            }
        }
    }
    int dx[4] = { 0, 0, -1, 1 };
    int dy[4] = { -1, 1, 0, 0 };
    while (q.size()) {
        auto cur = q.front();
        q.pop();
        int curx = cur.first, cury = cur.second;
        for (int i = 0; i < 4; i++) {
            int x = curx + dx[i], y = cury + dy[i];
            if (x >= 0 and x < n and y >= 0 and y < m
                and c[x][y] != 'N'
                and res[x][y] > res[curx][cury] + 1) {
                q.push({ x, y });
                res[x][y] = res[curx][cury] + 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (c[i][j] == '.')
                res[i][j] = 0;
            else if (res[i][j] == 1e9 and c[i][j] != 'N')
                res[i][j] = -1;
            else if (res[i][j] == 1e9 and c[i][j] != 'H')
                res[i][j] = 0;
            else
                res[i][j] *= 2;
        }
    }
    return res;
}

// Drivers code
int main()
{

    int n = 3, 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);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Time Complexity: O(n*m + n*m) At first As each cell of the matrix is visited only once during the BFS traversal. Finally, the algorithm iterates over the matrix again to calculate the minimum distance from each house to the well.
Auxiliary Space: O(n*m) + O(n*m) + O(n*m) = O(n*m) The algorithm uses a 2D boolean array of size nm to keep track of visited cells during the BFS traversal. It also uses a queue to store the cells to be visited during the BFS traversal, which can contain up to nm elements in the worst case. Additionally, it uses a 2D integer array of size n*m to store the minimum distance of each house from the well.

Last Updated :
11 May, 2023

Like Article

Save Article