You are given a 2D grid representing a house, with rooms labeled as 'INF' for empty rooms, -1 for walls, and 0 for gates. You need to fill each empty room with the distance to the nearest gate. If it is impossible to reach a gate, leave the room labeled as 'INF'.
Note: In this problem, the distance is measured by the number of steps required to reach the nearest gate, considering only empty rooms and moving up, down, left, and right.
Table of Contents
Sample Input:
Grid:
[
[INF, -1, 0, INF],
[INF, INF, INF, -1],
[INF, -1, INF, -1],
[ 0, -1, INF, INF]
]
Expected Output:
Grid:
[
[ 3, -1, 0, 1],
[ 2, 2, 1, -1],
[ 1, -1, 2, -1],
[ 0, -1, 3, 4]
]
In this example, the rooms will be filled with the distance to the nearest gate, considering only empty rooms and moving up, down, left, and right.
Time and Space Complexity:
The time complexity of the algorithm is O(m * n), where ‘m’ is the number of rows and ‘n’ is the number of columns in the grid. In the worst case, we may have to visit each cell once to calculate the distance to the nearest gate. The space complexity is O(m * n) as well, due to the recursion stack and the queue used for the BFS, which can grow to the size of the grid in the worst case.
C++ solution:
#include <iostream>
#include <vector>
#include <queue>
void wallsAndGates(std::vector<std::vector<int>>& rooms) {
int rows = rooms.size();
if (rows == 0) return;
int cols = rooms[0].size();
if (cols == 0) return;
// Define the four possible directions: up, down, left, right
std::vector<int> directions = {0, 1, 0, -1, 0};
// Perform a breadth-first search (BFS) starting from each gate
std::queue<std::pair<int, int>> q;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (rooms[i][j] == 0) {
// Enqueue all gates to start the BFS from each gate
q.push({i, j});
}
}
}
// Start the BFS from each gate
while (!q.empty()) {
int i = q.front().first;
int j = q.front().second;
q.pop();
// Explore all four directions (up, down, left, right) from the current room
for (int k = 0; k < 4; ++k) {
int newRow = i + directions[k];
int newCol = j + directions[k + 1];
// If the new position is valid and has a larger distance than the current room,
// update its distance and enqueue it for further exploration.
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&
rooms[newRow][newCol] > rooms[i][j] + 1) {
rooms[newRow][newCol] = rooms[i][j] + 1;
q.push({newRow, newCol});
}
}
}
}
int main() {
// Construct the grid for the sample input
std::vector<std::vector<int>> grid = {
{INT_MAX, -1, 0, INT_MAX},
{INT_MAX, INT_MAX, INT_MAX, -1},
{INT_MAX, -1, INT_MAX, -1},
{0, -1, INT_MAX, INT_MAX}
};
// Apply the walls and gates algorithm to fill the rooms with distances
wallsAndGates(grid);
// Print the result
std::cout << "Result:" << std::endl;
for (const auto& row : grid) {
std::cout << "[";
for (int i = 0; i < row.size(); ++i) {
std::cout << row[i];
if (i < row.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
return 0;
}
The wallsAndGates function performs a breadth-first search (BFS) starting from each gate (‘0’) and updates the distance to the nearest gate for each empty room (‘INF’). It uses a queue to explore all rooms in a breadth-first manner, and it updates the distance of neighboring rooms if a shorter path is found.
In the given example, the function will correctly fill the rooms with the distance to the nearest gate, and the output will be as follows:
Result:
[3, -1, 0, 1]
[2, 2, 1, -1]
[1, -1, 2, -1]
[0, -1, 3, 4]