-
Notifications
You must be signed in to change notification settings - Fork 0
/
1001.网格照明.c
76 lines (69 loc) · 2.29 KB
/
1001.网格照明.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
* @lc app=leetcode.cn id=1001 lang=c
*
* [1001] 网格照明
*
* https://leetcode-cn.com/problems/grid-illumination/description/
*
* algorithms
* Hard (28.57%)
* Likes: 23
* Dislikes: 0
* Total Accepted: 1.2K
* Total Submissions: 4.3K
* Testcase Example: '5\n[[0,0],[4,4]]\n[[1,1],[1,0]]'
*
* 在 N x N 的网格上,每个单元格 (x, y) 上都有一盏灯,其中 0 <= x < N 且 0 <= y < N 。
*
* 最初,一定数量的灯是亮着的。lamps[i] 告诉我们亮着的第 i 盏灯的位置。每盏灯都照亮其所在 x 轴、y
* 轴和两条对角线上的每个正方形(类似于国际象棋中的皇后)。
*
* 对于第 i 次查询 queries[i] = (x, y),如果单元格 (x, y) 是被照亮的,则查询结果为 1,否则为 0 。
*
* 在每个查询 (x, y) 之后 [按照查询的顺序],我们关闭位于单元格 (x, y) 上或其相邻 8 个方向上(与单元格 (x, y)
* 共享一个角或边)的任何灯。
*
* 返回答案数组 answer。每个值 answer[i] 应等于第 i 次查询 queries[i] 的结果。
*
*
*
* 示例:
*
* 输入:N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
* 输出:[1,0]
* 解释:
* 在执行第一次查询之前,我们位于 [0, 0] 和 [4, 4] 灯是亮着的。
* 表示哪些单元格亮起的网格如下所示,其中 [0, 0] 位于左上角:
* 1 1 1 1 1
* 1 1 0 0 1
* 1 0 1 0 1
* 1 0 0 1 1
* 1 1 1 1 1
* 然后,由于单元格 [1, 1] 亮着,第一次查询返回 1。在此查询后,位于 [0,0] 处的灯将关闭,网格现在如下所示:
* 1 0 0 0 1
* 0 1 0 0 1
* 0 0 1 0 1
* 0 0 0 1 1
* 1 1 1 1 1
* 在执行第二次查询之前,我们只有 [4, 4] 处的灯亮着。现在,[1, 0] 处的查询返回 0,因为该单元格不再亮着。
*
*
*
*
* 提示:
*
*
* 1 <= N <= 10^9
* 0 <= lamps.length <= 20000
* 0 <= queries.length <= 20000
* lamps[i].length == queries[i].length == 2
*
*
*/
// @lc code=start
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* gridIllumination(int N, int** lamps, int lampsSize, int* lampsColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){
}
// @lc code=end