在无限大的2维平面上有 n
种不同的病毒。给定二维数组 points
,第 i
项 points[i] = [xi, yi]
说明第 0
天有一种病毒在点 (xi, yi)
。注意初始状态下,可能有多种病毒在同一点上。
每天,被感染的点会把它感染的病毒传播到上下左右四个邻居点。
现给定一个整数k
,问最少需要多少天,方能找到一点感染至少 k
种病毒?
示例 1:
输入:points = [[1,1],[6,1]], k = 2 输出:3 解释:在第3天,点 (3,1) 与 (4,1) 将感染所有2种病毒。
示例 2:
输入:points = [[3,3],[1,2],[9,2]], k = 2 输出:2 解释:在第2天, 点(1,2), (1,3), (2,1), (2,2), (3,1) 和 (3,3) 将会感染前两种病毒。
示例 3:
输入:points = [[3,3],[1,2],[9,2]], k = 3 输出: 4 解释:在第4天,点 (5,2) 会感染所有3种病毒。
提示:
n == points.length
2 <= n <= 16
1 <= xi, yi <= 109
2 <= k <= n