0764. Largest Plus Sign¶
题目信息¶
- 题号:
0764
- 难度:
Medium
- 主题:
矩阵、十字形、最大阶数
- 原题:
- 重点:
网格除
mines指定位置为 0 外均为 1;阶数k包含中心及四条长度为k - 1的轴向手臂,只检查十字覆盖位置
题目重述¶
建立一个 n x n 二进制网格,初始所有位置都为 1;数组 mines 中每个不同坐标 [x, y] 指定该格为 0。
一个与行列方向对齐、阶数为 k 的加号由一个值为 1 的中心格,以及向上、下、左、右各延伸 k - 1 个值为 1 的格子组成。手臂终点之外的格子可以是 0 或 1,不影响该加号是否合法。
请返回网格中最大合法加号的阶数;若连阶数为 1 的加号都不存在,返回 0。
1 <= n <= 500,1 <= mines.length <= 5000;所有坐标互不重复,并满足 0 <= x, y < n。
自建示例¶
中心可以形成三阶加号:
输入:n = 5, mines = [[0,0],[4,4]]
输出:3
解释:以 (2,2) 为中心,向四个方向各延伸两个格子时,十字覆盖位置全部为 1,因此存在三阶加号。四阶加号需要更长的手臂,5 x 5 网格无法容纳。
只剩一个可用格子时最大阶数为一:
输入:n = 2, mines = [[0,0],[0,1],[1,0]]
输出:1
解释:网格中只有位置 (1,1) 的值为 1,它可以作为没有延伸手臂的一阶加号中心;不存在第二个值为 1 的格子,更不可能形成二阶加号。