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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MaxDistance(int[][] grid) {
6 int n = grid.Length;
7 Queue<(int, int)> queue = new Queue<(int, int)>();
8 bool hasWater = false;
9
10 for (int i = 0; i < n; i++) {
11 for (int j = 0; j < n; j++) {
12 if (grid[i][j] == 1) {
13 queue.Enqueue((i, j));
14 } else {
15 hasWater = true;
16 }
17 }
18 }
19
20 if (queue.Count == n * n || !hasWater) return -1;
21
22 int distance = -1;
23 int[][] directions = { new int[]{1, 0}, new int[]{-1, 0}, new int[]{0, 1}, new int[]{0, -1} };
24
25 while (queue.Count > 0) {
26 int size = queue.Count;
27 for (int k = 0; k < size; k++) {
28 var (x, y) = queue.Dequeue();
29 foreach (var dir in directions) {
30 int nx = x + dir[0];
31 int ny = y + dir[1];
32 if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
33 grid[nx][ny] = 1;
34 queue.Enqueue((nx, ny));
35 }
36 }
37 }
38 distance++;
39 }
40
41 return distance;
42 }
43}
44The C# solution utilizes a queue to implement a BFS on the grid, starting from land cells and iterating until all reachable water cells are converted into land, measuring the BFS depth for distance.