class Solution {
  private final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

  private boolean inBounds(int[][] graph, int y, int x) {
    int n = graph.length;
    return y >= 0 && y < n && x >= 0 && x < n;
  }

  private void setSafeness(int[][] graph, Queue<int[]> queue) {
    while (!queue.isEmpty()) {
      int size = queue.size();

      while (size-- > 0) {
        int[] cell = queue.poll();
        int y = cell[0], x = cell[1];

        for (int[] d : DIRECTIONS) {
          int ny = y + d[0];
          int nx = x + d[1];

          int value = graph[y][x];

          if (inBounds(graph, ny, nx) && graph[ny][nx] == -1) {
            graph[ny][nx] = value + 1;
            queue.add(new int[] {ny, nx});
          }
        }
      }
    }
  }

  private int[][] toGraph(List<List<Integer>> grid) {
    int n = grid.size();

    int[][] graph = new int[n][n];

    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < n * n; ++i) {
      int y = i / n;
      int x = i % n;

      if (grid.get(y).get(x) == 1) {
        queue.add(new int[] {y, x});
        graph[y][x] = 0;
      } else {
        graph[y][x] = -1;
      }
    }

    // calculate safeness
    setSafeness(graph, queue);

    return graph;
  }

  private int safestPath(int[][] graph) {
    int n = graph.length;

    PriorityQueue<int[]> pq = new PriorityQueue<>((l, r) -> r[2] - l[2]);

    pq.add(new int[] {0, 0, graph[0][0]});
    graph[0][0] = -1;

    while (!pq.isEmpty()) {
      int[] next = pq.poll();

      int y = next[0], x = next[1], safeness = next[2];

      // found the goal
      if (y == n - 1 && x == n - 1) {
        return safeness;
      }

      for (int[] d : DIRECTIONS) {
        int ny = y + d[0];
        int nx = x + d[1];

        if (inBounds(graph, ny, nx) && graph[ny][nx] != -1) {
          pq.add(new int[] {ny, nx, Math.min(safeness, graph[ny][nx])});
          graph[ny][nx] = -1;
        }
      }
    }

    return -1;
  }

  public int maximumSafenessFactor(List<List<Integer>> grid) {
    int n = grid.size();
    int[][] graph = toGraph(grid);
    return safestPath(graph);
  }
}