Sponsored
Sponsored
This approach uses BFS starting from all land cells simultaneously. We can think of the lands spreading out like waves in unison into the water cells, each wave representing a unit of distance. This helps us efficiently compute the farthest distance of a water cell from land.
The time complexity is O(n2), where n is the dimension of the grid, as each cell is visited once. The space complexity is also O(n2) due to the queue that can store all cells in the grid.
1#include <vector>
2#include <queue>
3#include <utility>
4using namespace std;
5
6int maxDistance(vector<vector<int>>& grid) {
7 int n = grid.size();
8 queue<pair<int, int>> q;
9 int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
10 bool hasWater = false;
11
12 for (int i = 0; i < n; i++) {
13 for (int j = 0; j < n; j++) {
14 if (grid[i][j] == 1) {
15 q.push({i, j});
16 } else {
17 hasWater = true;
18 }
19 }
20 }
21
22 if (q.size() == n * n || !hasWater) return -1;
23
24 int distance = -1;
25 while (!q.empty()) {
26 int size = q.size();
27 while (size--) {
28 auto [x, y] = q.front();
29 q.pop();
30 for (auto& d : directions) {
31 int nx = x + d[0], ny = y + d[1];
32 if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
33 grid[nx][ny] = 1;
34 q.push({nx, ny});
35 }
36 }
37 }
38 distance++;
39 }
40
41 return distance;
42}
43The solution initializes a queue with all land cells and proceeds with a BFS. Each cell, when processed, transforms its neighboring water cells into land cells and is pushed into the queue. The number of BFS iterations determines the maximum distance.