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 <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5#define MAXN 100
6
7int maxDistance(int** grid, int gridSize, int* gridColSize) {
8 int n = gridSize;
9 int queue[MAXN * MAXN][2];
10 int front = 0, rear = 0;
11 int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
12 bool hasWater = false;
13
14 for (int i = 0; i < n; i++) {
15 for (int j = 0; j < n; j++) {
16 if (grid[i][j] == 1) {
17 queue[rear][0] = i;
18 queue[rear][1] = j;
19 rear++;
20 } else {
21 hasWater = true;
22 }
23 }
24 }
25
26 if (rear == n * n || !hasWater) return -1;
27
28 int distance = -1;
29 while (front < rear) {
30 int size = rear - front;
31 while (size--) {
32 int x = queue[front][0];
33 int y = queue[front][1];
34 front++;
35
36 for (int d = 0; d < 4; d++) {
37 int nx = x + directions[d][0];
38 int ny = y + directions[d][1];
39
40 if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
41 grid[nx][ny] = 1;
42 queue[rear][0] = nx;
43 queue[rear][1] = ny;
44 rear++;
45 }
46 }
47 }
48 distance++;
49 }
50
51 return distance;
52}
53The function uses a queue to implement BFS starting from all land cells. The queue holds the coordinates of the cells to be processed next. It explores all grid cells using BFS and calculates the maximum distance from the nearest land cell to a water cell.