Given an n x ngrid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
Example 1:
Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.
Example 2:
Input: grid = [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.
Solution: (Brute Force)
Approach:
Finding the nearest land to each water cell
Finding the maximum of all nearest distance
class Solution
{
public:
int dfs(vector<vector<int>> &grid, int x, int y)
{
int near = INT_MAX;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == 1)
{
int dist = abs(x - i) + abs(y - j);
near = min(near, dist);
}
}
}
return near;
}
int maxDistance(vector<vector<int>> &grid)
{
int res = INT_MIN;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == 0)
{
int dist = dfs(grid, i, j);
res = max(res, dist);
}
}
}
if(res == INT_MAX || res == INT_MIN){
return -1;
}
return res;
}
};
Time Complexity: O(n^2 * n^2)
Solution: (BFS)
Approach:
Starting BFS from land cell and increasing distance
class Solution
{
public:
void bfs(vector<vector<int>> &grid, queue<pair<int, int>> &q)
{
vector<int> dir{0, 1, 0, -1, 0};
int n = grid.size();
while (!q.empty())
{
int i = q.front().first;
int j = q.front().second;
q.pop();
for (int k = 0; k < 4; k++)
{
int x = i + dir[k];
int y = j + dir[k + 1];
if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] == 0)
{
grid[x][y] = grid[i][j] + 1;
q.push({x, y});
}
}
}
return;
}
int maxDistance(vector<vector<int>> &grid)
{
queue<pair<int, int>> q;
int n = grid.size();
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == 1)
{
q.push({i, j});
}
}
}
if (q.size() == 0 || q.size() == n * n)
{
return -1;
}
bfs(grid, q);
int res = INT_MIN;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] > res)
{
res = grid[i][j];
}
}
}
return res-1;
}
};
Runtime: O(n * n). We process an individual cell only once (or twice).
Memory: O(n) for the queue.
