Last Day Where You Can Still Cross LeetCode solution in Java

1
class Solution {
2
  int[][] dir = new int[][] {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
3

4
  public int latestDayToCross(int row, int col, int[][] cells) {
5
    int grid[][] = new int[row][col];
6
    int low = 0, high = cells.length - 1;
7
    int ans = 0;
8

9
    while (low <= high) {
10
      int mid = low + (high - low) / 2;
11

12
      for (int i = 0; i <= mid; i++) grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
13

14
      if (helper(grid, new boolean[row][col])) {
15
        ans = mid;
16
        low = mid + 1;
17
      } else high = mid - 1;
18

19
      for (int i = 0; i < grid.length; i++) for (int j = 0; j < grid[i].length; j++) grid[i][j] = 0;
20
    }
21

22
    return ans + 1;
23
  }
24

25
  public boolean helper(int[][] grid, boolean[][] visited) {
26
    for (int i = 0; i < grid[0].length; i++)
27
      if (grid[0][i] == 0 && !visited[0][i] && safe(0, i, grid, visited)) return true;
28
    return false;
29
  }
30

31
  public boolean safe(int i, int j, int[][] cells, boolean[][] visited) {
32
    if (i < 0
33
        || j < 0
34
        || i >= visited.length
35
        || j >= visited[i].length
36
        || visited[i][j]
37
        || cells[i][j] == 1) return false;
38
    if (i == cells.length - 1 && j < cells[i].length && cells[i][j] == 0) return true;
39

40
    visited[i][j] = true;
41
    for (int k = 0; k < dir.length; k++)
42
      if (safe(i + dir[k][0], j + dir[k][1], cells, visited)) return true;
43
    return false;
44
  }
45
}