Question

764. Largest Plus Sign

中文文档

Description

You are given an integer n. You have an n x n binary grid grid with all values initially 1's except for some indices given in the array mines. The ith element of the array mines is defined as mines[i] = [xi, yi] where grid[xi][yi] == 0.

Return _the order of the largest axis-aligned plus sign of _1_'s contained in _grid. If there is none, return 0.

An axis-aligned plus sign of 1's of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1's. Note that there could be 0's or 1's beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1's.

 

Example 1:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

Example 2:

Input: n = 1, mines = [[0,0]]
Output: 0
Explanation: There is no plus sign, so return 0.

 

Constraints:

• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• All the pairs (xi, yi) are unique.

Solutions

Solution 1

class Solution:
  def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
    dp = [[n] * n for _ in range(n)]
    for x, y in mines:
      dp[x][y] = 0
    for i in range(n):
      left = right = up = down = 0
      for j, k in zip(range(n), reversed(range(n))):
        left = left + 1 if dp[i][j] else 0
        right = right + 1 if dp[i][k] else 0
        up = up + 1 if dp[j][i] else 0
        down = down + 1 if dp[k][i] else 0
        dp[i][j] = min(dp[i][j], left)
        dp[i][k] = min(dp[i][k], right)
        dp[j][i] = min(dp[j][i], up)
        dp[k][i] = min(dp[k][i], down)
    return max(max(v) for v in dp)

class Solution {
  public int orderOfLargestPlusSign(int n, int[][] mines) {
    int[][] dp = new int[n][n];
    for (var e : dp) {
      Arrays.fill(e, n);
    }
    for (var e : mines) {
      dp[e[0]][e[1]] = 0;
    }
    for (int i = 0; i < n; ++i) {
      int left = 0, right = 0, up = 0, down = 0;
      for (int j = 0, k = n - 1; j < n; ++j, --k) {
        left = dp[i][j] > 0 ? left + 1 : 0;
        right = dp[i][k] > 0 ? right + 1 : 0;
        up = dp[j][i] > 0 ? up + 1 : 0;
        down = dp[k][i] > 0 ? down + 1 : 0;
        dp[i][j] = Math.min(dp[i][j], left);
        dp[i][k] = Math.min(dp[i][k], right);
        dp[j][i] = Math.min(dp[j][i], up);
        dp[k][i] = Math.min(dp[k][i], down);
      }
    }
    return Arrays.stream(dp).flatMapToInt(Arrays::stream).max().getAsInt();
  }
}

class Solution {
public:
  int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
    vector<vector<int>> dp(n, vector<int>(n, n));
    for (auto& e : mines) dp[e[0]][e[1]] = 0;
    for (int i = 0; i < n; ++i) {
      int left = 0, right = 0, up = 0, down = 0;
      for (int j = 0, k = n - 1; j < n; ++j, --k) {
        left = dp[i][j] ? left + 1 : 0;
        right = dp[i][k] ? right + 1 : 0;
        up = dp[j][i] ? up + 1 : 0;
        down = dp[k][i] ? down + 1 : 0;
        dp[i][j] = min(dp[i][j], left);
        dp[i][k] = min(dp[i][k], right);
        dp[j][i] = min(dp[j][i], up);
        dp[k][i] = min(dp[k][i], down);
      }
    }
    int ans = 0;
    for (auto& e : dp) ans = max(ans, *max_element(e.begin(), e.end()));
    return ans;
  }
};

func orderOfLargestPlusSign(n int, mines [][]int) (ans int) {
  dp := make([][]int, n)
  for i := range dp {
    dp[i] = make([]int, n)
    for j := range dp[i] {
      dp[i][j] = n
    }
  }
  for _, e := range mines {
    dp[e[0]][e[1]] = 0
  }
  for i := 0; i < n; i++ {
    var left, right, up, down int
    for j, k := 0, n-1; j < n; j, k = j+1, k-1 {
      left, right, up, down = left+1, right+1, up+1, down+1
      if dp[i][j] == 0 {
        left = 0
      }
      if dp[i][k] == 0 {
        right = 0
      }
      if dp[j][i] == 0 {
        up = 0
      }
      if dp[k][i] == 0 {
        down = 0
      }
      dp[i][j] = min(dp[i][j], left)
      dp[i][k] = min(dp[i][k], right)
      dp[j][i] = min(dp[j][i], up)
      dp[k][i] = min(dp[k][i], down)
    }
  }
  for _, e := range dp {
    ans = max(ans, slices.Max(e))
  }
  return
}