764.最大加号标志.md

764.最大加号标志

/*
 * @lc app=leetcode.cn id=764 lang=typescript
 *
 * [764] 最大加号标志
 */

// @lc code=start
function orderOfLargestPlusSign(n: number, mines: number[][]): number {}
// @lc code=end

解法 1: 枚举

function orderOfLargestPlusSign(n: number, mines: number[][]): number {
  const len: number[][] = Array.from({ length: n }, () => new Array(n).fill(0))
  const g: number[][] = Array.from({ length: n }, () => new Array(n).fill(1))
  for (let [i, j] of mines) g[i][j] = 0
  for (let i = 0; i < n; i++) {
    for (let j = 0, k = 0; j < n; j = ++k) {
      if (g[i][j] === 0) continue
      while (g[i][k + 1]) k++
      for (let l = j; l <= k; l++) {
        len[i][l] = Math.min(l - j + 1, k - l + 1)
      }
    }
  }
  let res = 0
  for (let i = 0; i < n; i++) {
    for (let j = 0, k = 0; j < n; j = ++k) {
      if (g[j][i] === 0) continue
      while (g[k + 1]?.[i]) k++
      for (let l = j; l <= k; l++) {
        res = Math.max(res, Math.min(len[l][i], l - j + 1, k - l + 1))
      }
    }
  }
  return res
}

Case

test.each([
  { input: { n: 5, mines: [[4, 2]] }, output: 2 },
  { input: { n: 1, mines: [[0, 0]] }, output: 0 },
])('input: n = $input.n, mines = $input.mines', ({ input: { n, mines }, output }) => {
  expect(orderOfLargestPlusSign(n, mines)).toEqual(output)
})