2023-06-26：在大小为 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 表示未照亮。

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

输出：[1,0]。

答案2023-06-26：

大体步骤如下：

1.首先，定义一个存储灯位置的二维数组 lamps，和查询位置的二维数组 queries。

2.创建四个map，用于记录每行、每列、左上到右下对角线和右上到左下对角线上的灯的数量。还有一个points map，用于存储所有点的状态。

3.遍历灯的位置，将灯的状态记录到相关的map中，并将点的状态记录到points map中。

4.创建一个结果数组 ans，用于存储每个查询的结果。

5.对于每一个查询位置，初始化结果为0。

6.如果查询位置所在的行、列、左上到右下对角线或者右上到左下对角线上有灯，将结果设为1。

7.遍历查询位置周围的8个方向，如果有灯，则关闭该灯，并在相关的map中减去相应的数量。

8.返回结果数组 ans。

时间复杂度分析:

• 遍历灯的位置并初始化maps需要 O(lamps)，其中 lamps 是灯的数量。

• 对于每个查询位置，遍历周围的8个方向，检查是否有灯需要 O(1) 的时间。

• 因此，总的时间复杂度为 O(lamps + queries)。

空间复杂度分析:

• maps 和 points 的空间复杂度均为 O(lamps)，其中 lamps 是灯的数量。

• 结果数组 ans 的空间复杂度为 O(queries)，其中 queries 是查询的数量。

• 因此，总的空间复杂度为 O(lamps + queries)。

go完整代码如下：

package main

import "fmt"

var move = [][]int{
    {0, 0},
    {0, -1},
    {0, 1},
    {-1, 0},
    {-1, -1},
    {-1, 1},
    {1, 0},
    {1, -1},
    {1, 1},
}

func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
    limit := int64(n)
    row := make(map[int]int)
    col := make(map[int]int)
    leftUpDiag := make(map[int]int)
    rightUpDiag := make(map[int]int)
    points := make(map[int64]bool)

    for _, p := range lamps {
        if points[limit*int64(p[0])+int64(p[1])] == false {
            points[limit*int64(p[0])+int64(p[1])] = true
            row[p[0]]++
            col[p[1]]++
            leftUpDiag[p[0]-p[1]]++
            rightUpDiag[p[0]+p[1]]++
        }
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        ans[i] = 0
        if row[q[0]] != 0 || col[q[1]] != 0 || leftUpDiag[q[0]-q[1]] != 0 || rightUpDiag[q[0]+q[1]] != 0 {
            ans[i] = 1
        }
        for _, m := range move {
            r := q[0] + m[0]
            c := q[1] + m[1]
            lu := r - c
            ru := r + c
            if r < 0 || r >= n || c < 0 || c >= n {
                continue
            }
            if points[limit*int64(r)+int64(c)] {
                points[limit*int64(r)+int64(c)] = false
                minusOrRemove(row, r)
                minusOrRemove(col, c)
                minusOrRemove(leftUpDiag, lu)
                minusOrRemove(rightUpDiag, ru)
            }
        }
    }

    return ans
}

func minusOrRemove(m map[int]int, key int) {
    if m[key] == 1 {
        delete(m, key)
    } else {
        m[key]--
    }
}

func main() {
    n := 5
    lamps := [][]int{{0, 0}, {4, 4}}
    queries := [][]int{{1, 1}, {1, 0}}
    result := gridIllumination(n, lamps, queries)
    fmt.Println(result)
}

rust完整代码如下：

use std::collections::{HashMap, HashSet};

fn grid_illumination(n: i32, lamps: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let limit = n;
    let mut row = HashMap::new();
    let mut col = HashMap::new();
    let mut left_up_diag = HashMap::new();
    let mut right_up_diag = HashMap::new();
    let mut points = HashSet::new();

    for p in lamps {
        if points.insert(limit * p[0] + p[1]) {
            *row.entry(p[0]).or_insert(0) += 1;
            *col.entry(p[1]).or_insert(0) += 1;
            *left_up_diag.entry(p[0] - p[1]).or_insert(0) += 1;
            *right_up_diag.entry(p[0] + p[1]).or_insert(0) += 1;
        }
    }

    let mut ans = Vec::with_capacity(queries.len());

    for q in queries {
        let mut illumination = 0;

        if row.contains_key(&q[0])
            || col.contains_key(&q[1])
            || left_up_diag.contains_key(&(q[0] - q[1]))
            || right_up_diag.contains_key(&(q[0] + q[1]))
        {
            illumination = 1;
        }

        for m in vec![
            vec![0, 0],
            vec![0, -1],
            vec![0, 1],
            vec![-1, 0],
            vec![-1, -1],
            vec![-1, 1],
            vec![1, 0],
            vec![1, -1],
            vec![1, 1],
        ] {
            let r = q[0] + m[0];
            let c = q[1] + m[1];
            let lu = r - c;
            let ru = r + c;

            if r < 0 || r >= n || c < 0 || c >= n {
                continue;
            }

            if points.contains(&(limit * r + c)) {
                points.remove(&(limit * r + c));
                minus_or_remove(&mut row, r);
                minus_or_remove(&mut col, c);
                minus_or_remove(&mut left_up_diag, lu);
                minus_or_remove(&mut right_up_diag, ru);
            }
        }

        ans.push(illumination);
    }

    ans
}

fn minus_or_remove(map: &mut HashMap<i32, i32>, key: i32) {
    if let Some(count) = map.get_mut(&key) {
        if *count == 1 {
            map.remove(&key);
        } else {
            *count -= 1;
        }
    }
}

fn main() {
    let n = 5;
    let lamps = vec![vec![0, 0], vec![4, 4]];
    let queries = vec![vec![1, 1], vec![1, 0]];

    let result = grid_illumination(n, lamps, queries);
    println!("{:?}", result);
}

c++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<vector<int>> move222 = {
    {0, 0},
    {0, -1},
    {0, 1},
    {-1, 0},
    {-1, -1},
    {-1, 1},
    {1, 0},
    {1, -1},
    {1, 1}
};

void minusOrRemove(unordered_map<int, int>& map, int key) {
    if (map[key] == 1)
        map.erase(key);
    else
        map[key]--;
}

vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
    long limit = n;
    unordered_map<int, int> row, col, leftUpDiag, rightUpDiag;
    unordered_set<long long> points;
    for (vector<int>& p : lamps) {
        if (points.insert(limit * p[0] + p[1]).second) {
            row[p[0]]++;
            col[p[1]]++;
            leftUpDiag[p[0] - p[1]]++;
            rightUpDiag[p[0] + p[1]]++;
        }
    }
    vector<int> ans(queries.size());
    int ansi = 0;
    for (vector<int>& q : queries) {
        ans[ansi++] = (row.count(q[0]) || col.count(q[1]) || leftUpDiag.count(q[0] - q[1]) || rightUpDiag.count(q[0] + q[1])) ? 1 : 0;
        for (vector<int>& m : move222) {
            int r = q[0] + m[0];
            int c = q[1] + m[1];
            int lu = r - c;
            int ru = r + c;
            if (r < 0 || r >= n || c < 0 || c >= n)
                continue;
            if (points.count(limit * r + c)) {
                points.erase(limit * r + c);
                minusOrRemove(row, r);
                minusOrRemove(col, c);
                minusOrRemove(leftUpDiag, lu);
                minusOrRemove(rightUpDiag, ru);
            }
        }
    }
    return ans;
}

int main() {
    int n = 5;
    vector<vector<int>> lamps = { {0, 0}, {4, 4} };
    vector<vector<int>> queries = { {1, 1}, {1, 0} };

    vector<int> result = gridIllumination(n, lamps, queries);

    for (const int& res : result) {
        cout << res << " ";
    }
    cout << endl;

    return 0;
}

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x;
    int y;
} Lamp;

int move[9][2] = {
    {0, 0},
    {0, -1},
    {0, 1},
    {-1, 0},
    {-1, -1},
    {-1, 1},
    {1, 0},
    {1, -1},
    {1, 1}
};

void minusOrRemove(int* map, int key) {
    if (map[key] == 1) {
        map[key] = 0;
    }
    else {
        map[key]--;
    }
}

int* gridIllumination(int n, Lamp* lamps, int lampsSize, int* lampsColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    long limit = n;
    int* row = (int*)calloc(n, sizeof(int));
    int* col = (int*)calloc(n, sizeof(int));
    int* leftUpDiag = (int*)calloc(2 * n - 1, sizeof(int));
    int* rightUpDiag = (int*)calloc(2 * n - 1, sizeof(int));
    int* points = (int*)calloc(n * n, sizeof(int));

    for (int i = 0; i < lampsSize; i++) {
        int x = lamps[i].x;
        int y = lamps[i].y;
        if (points[limit * x + y] == 0) {
            points[limit * x + y] = 1;
            row[x]++;
            col[y]++;
            leftUpDiag[x - y + n - 1]++;
            rightUpDiag[x + y]++;
        }
    }

    int* ans = (int*)calloc(queriesSize, sizeof(int));

    for (int i = 0; i < queriesSize; i++) {
        int x = queries[i][0];
        int y = queries[i][1];

        ans[i] = (row[x] || col[y] || leftUpDiag[x - y + n - 1] || rightUpDiag[x + y]) ? 1 : 0;

        for (int j = 0; j < 9; j++) {
            int r = x + move[j][0];
            int c = y + move[j][1];
            int lu = r - c + n - 1;
            int ru = r + c;

            if (r < 0 || r >= n || c < 0 || c >= n) {
                continue;
            }

            if (points[limit * r + c] == 1) {
                points[limit * r + c] = 0;
                minusOrRemove(row, r);
                minusOrRemove(col, c);
                minusOrRemove(leftUpDiag, lu);
                minusOrRemove(rightUpDiag, ru);
            }
        }
    }

    free(row);
    free(col);
    free(leftUpDiag);
    free(rightUpDiag);
    free(points);

    *returnSize = queriesSize;
    return ans;
}

int main() {
    int n = 5;
    int lampsSize = 2;
    int lampsColSize[2] = { 2, 2 };
    Lamp lamps[2] = { {0, 0}, {4, 4} };

    int queriesSize = 2;
    int queriesColSize[2] = { 2, 2 };
    int** queries = (int**)malloc(queriesSize * sizeof(int*));
    for (int i = 0; i < queriesSize; i++) {
        queries[i] = (int*)malloc(2 * sizeof(int));
    }
    queries[0][0] = 1;
    queries[0][1] = 1;
    queries[1][0] = 1;
    queries[1][1] = 0;

    int returnSize;
    int* result = gridIllumination(n, lamps, lampsSize, lampsColSize, queries, queriesSize, queriesColSize, &returnSize);

    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    for (int i = 0; i < queriesSize; i++) {
        free(queries[i]);
    }
    free(queries);
    free(result);

    return 0;
}