As Far from Land as Possible LeetCode solution in Java

1
class Solution {
2
  class Point {
3
    int x, y;
4

5
    public Point(int x, int y) {
6
      this.x = x;
7
      this.y = y;
8
    }
9
  }
10

11
  int[][] dist;
12
  int n, ans;
13
  int[] dx = {0, 0, +1, -1};
14
  int[] dy = {+1, -1, 0, 0};
15

16
  public int maxDistance(int[][] grid) {
17
    n = grid.length;
18
    dist = new int[n][n];
19
    Queue<Point> q = new LinkedList<>();
20
    for (int i = 0; i < n; i++) {
21
      for (int j = 0; j < n; j++) {
22
        if (grid[i][j] == 0) dist[i][j] = 2 * 1000 * 1000 * 1000;
23
        else {
24
          dist[i][j] = 0;
25
          q.add(new Point(i, j)); // multisource on grid[i][j] = 1
26
        }
27
      }
28
    }
29
    ans = -1;
30
    while (!q.isEmpty()) {
31
      Point p = q.poll();
32
      int x = p.x;
33
      int y = p.y;
34
      for (int k = 0; k < 4; k++) {
35
        int r = dx[k] + x;
36
        int c = dy[k] + y;
37
        if (valid(r, c) && grid[r][c] == 0 && dist[r][c] > dist[x][y] + 1) {
38
          dist[r][c] = dist[x][y] + 1;
39
          Point newP = new Point(r, c);
40
          q.add(newP);
41
        }
42
      }
43
    }
44
    for (int i = 0; i < n; i++) {
45
      for (int j = 0; j < n; j++) {
46
        ans =
47
            Math.max(
48
                ans,
49
                dist[i][
50
                    j]); // Manhattan distance is the same as the distance on the grid in general
51
      }
52
    }
53
    if (ans == 0 || ans == 2 * 1000 * 1000 * 1000) ans = -1;
54
    return ans;
55
  }
56

57
  public boolean valid(int r, int c) {
58
    return r >= 0 && c >= 0 && r < n && c < n;
59
  }
60
}