1001. 网格照明

网格照明"/>

1001. 网格照明

1001. 网格照明

难度困难98

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。

示例 1：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。

第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]

示例 3：

输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]

提示：

• 1 <= n <= 109
• 0 <= lamps.length <= 20000
• 0 <= queries.length <= 20000
• lamps[i].length == 2
• 0 <= rowi, coli < n
• queries[j].length == 2
• 0 <= rowj, colj < n

在解决这个问题前，我们先弱化一下题目难度，找找思路

假设现在我们可以认为lamps中不会存在重复的元素(即不会有一个位置存在灯这个情况出现两次)，同时假设queries[j]之后不会进行灭灯的操作。

思路一：首先读题，一个亮的灯泡可以同时点亮其所在行、列、主副对角线上的位置。值得注意的是，一个位置亮的条件是只需要有一个灯泡照亮它即可；也就是说一个位置可能会被多个灯泡点亮。朴素的思路是我们开一个数组lighted_num[i][j]用于记录位置(i,j)被点亮的次数，当某一个灯泡亮的时候，将其同行、列、主副对角线上的所有位置的被点亮次数+1；若某一个灯泡被熄灭则将同行、列、主副对角线上的所有位置的被点亮次数-1，查询该位置是否亮则等价于该位置的被点亮次数是否大于1。来看一下数据规模，n最大为10^9，在存储上存在困难；另外按照上述更新策略，每次点亮一个灯泡，需要O(4*N)的复杂度来更新被点亮次数。

思路二：从N皇后问题中收到启发，该题和N皇后问题很类似，可以借鉴其思想。

采用记数数组的方式记录行、列、正副对角线被点亮的次数：

lighted_row_num：某一行被点亮的次数。

lighted_col_num：某一列被点亮的次数。

lighted_diagonal_num：对于正对角线，我们取一条来看看：(0,1)->(1,2)->(2,3)，因此我们可以发现row-col是一个定值，通过这个定值就可以确定一条正对角线；在实际实现的时候，为了避免负数导致索引越界，因此可以加上一个偏置值。

lighted_counter_diagonal_num：对于副对角线，同理也取一条来看看：(2,0)->(1,1)->(0,2)，会发现row+col是一个定值，可以确定一条副对角线。

因此判断[i][j]位置是否被点亮只需要判断是否 lighted_row[i] + lighted_col[j] + diagonal[i - j + n] + counter_diagonal[i + j] > 0 即可。

class Solution {
public:vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {int rows_num = lamps.size(), cols_num = lamps[0].size(), i, j, row, col;int lighted_row_num[n + 5], lighted_col_num[n + 5], lighted_diagonal_num[(n << 1) + 5], lighted_counter_diagonal_num[(n << 1) + 5];memset(lighted_row_num, 0, sizeof(lighted_row_num));memset(lighted_col_num, 0, sizeof(lighted_col_num));memset(lighted_diagonal_num, 0, sizeof(lighted_diagonal_num));memset(lighted_counter_diagonal_num, 0, sizeof(lighted_counter_diagonal_num));for(vector<int> lamp : lamps){row = lamp[0], col = lamp[1];++ lighted_row_num[row];++ lighted_col_num[col];++ lighted_diagonal_num[row - col + n];++ lighted_counter_diagonal_num[row + col];}vector<int> lighted_res;for(vector<int> query : queries){row = query[0], col = query[1];if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col]){lighted_res.push_back(1);}else{lighted_res.push_back(0);}}return lighted_res;}
};

注：笔者在实现的时候并没有使用 lighted_row[i] + lighted_col[j] + diagonal[i - j + n] + counter_diagonal[i + j] > 0 的方式来判断点亮情况，而是采用 if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col])，这样做是考虑到每个位置点亮的次数必定是满足>=0的，因此用逻辑或的短路逻辑也许可以加快点判断(猜的)-_-||

现在我们来看看我们弱化题目时做的假设：

1.对于lamps中的重复点，我们可以进行打标记去重操作。

2.对于queries[j]查询后要灭灯的重操作，我们可以遍历查询点的8邻接点，如果有光源，则进行灭灯操作，操作方式无非就是将点亮方式减1。

queries.size() <= 20000，所以实际上查询点是离散的，为了节省空间，可以用哈希套哈希结构用于打光源标记。

以下代码有点超时，还在修改，估计是因为动态分配内存的问题-。-

class Solution {public:int dir[9][2] = {{-1, -1},{-1, 0},{-1, 1},{0, -1},{0, 0},{0, 1},{1, -1},{1, 0},{1, 1},};vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {unordered_map<int, unordered_set<int>> LightSource; int rows_num = lamps.size(), cols_num = lamps[0].size(), i, j, row, col, nrow, ncol;int *lighted_row_num = new int[n + 5](), *lighted_col_num = new int [n + 5](), *lighted_diagonal_num = new int[(n << 1) + 5](), *lighted_counter_diagonal_num = new int[(n << 1) + 5]();for(vector<int> lamp : lamps){row = lamp[0], col = lamp[1];if(LightSource.find(row) == LightSource.end()){unordered_set<int> hash_cols_index;LightSource[row] = hash_cols_index;}else if(LightSource[row].find(col) != LightSource[row].end()){continue; //去重}unordered_set<int> &cols_index = LightSource[row];cols_index.insert(col);++ lighted_row_num[row];++ lighted_col_num[col];++ lighted_diagonal_num[row - col + n];++ lighted_counter_diagonal_num[row + col];}vector<int> lighted_res;for(vector<int> query : queries){row = query[0], col = query[1];if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col]){lighted_res.push_back(1);}else{lighted_res.push_back(0);}for(i = 0; i < 9; ++ i){nrow = row + dir[i][0];ncol = col + dir[i][1];if(LightSource.find(nrow) != LightSource.end() && LightSource[nrow].find(ncol) != LightSource[nrow].end()){//存在光源 不用做越界判断是因为越界的数据不可能会在哈希表里-- lighted_row_num[nrow];-- lighted_col_num[ncol];-- lighted_diagonal_num[nrow - ncol + n];-- lighted_counter_diagonal_num[nrow + ncol];//从哈希表中删除LightSource[nrow].erase(ncol);}}}return lighted_res;}
};

现在我们回看数据规模，lamps.size() < 20000，也就是说，灯泡放置点实际上离散程度也很大，因此不用数组，考虑也是用哈希表，减轻动态分配内存带来的性能压力，终于过了-_-||

class Solution {public:int dir[9][2] = {{-1, -1},{-1, 0},{-1, 1},{0, -1},{0, 0},{0, 1},{1, -1},{1, 0},{1, 1},};vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {unordered_map<int, unordered_set<int>> LightSource; int rows_num = lamps.size(), cols_num = lamps[0].size(), i, j, row, col, nrow, ncol;unordered_map<int, int> lighted_row_num, lighted_col_num, lighted_diagonal_num, lighted_counter_diagonal_num;for(vector<int> lamp : lamps){row = lamp[0], col = lamp[1];if(LightSource.find(row) == LightSource.end()){unordered_set<int> hash_cols_index;LightSource[row] = hash_cols_index;}else if(LightSource[row].find(col) != LightSource[row].end()){continue; //去重}unordered_set<int> &cols_index = LightSource[row];cols_index.insert(col);++ lighted_row_num[row];++ lighted_col_num[col];++ lighted_diagonal_num[row - col + n];++ lighted_counter_diagonal_num[row + col];}vector<int> lighted_res;for(vector<int> query : queries){row = query[0], col = query[1];if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col]){lighted_res.push_back(1);}else{lighted_res.push_back(0);}for(i = 0; i < 9; ++ i){nrow = row + dir[i][0];ncol = col + dir[i][1];if(LightSource.find(nrow) != LightSource.end() && LightSource[nrow].find(ncol) != LightSource[nrow].end()){//存在光源 不用做越界判断是因为越界的数据不可能会在哈希表里-- lighted_row_num[nrow];-- lighted_col_num[ncol];-- lighted_diagonal_num[nrow - ncol + n];-- lighted_counter_diagonal_num[nrow + ncol];//从哈希表中删除LightSource[nrow].erase(ncol);}}}return lighted_res;}
};