Задача: 1001. Grid Illumination
Сложность: hard

Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный массив позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный массив queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. Верните массив целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.

Пример:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]

👨‍💻 Алгоритм:

1⃣Инициализация данных:
Используйте множества для хранения включенных ламп, освещенных строк, столбцов, диагоналей и обратных диагоналей.
Инициализируйте множества и словари для отслеживания количества ламп, освещающих каждую строку, столбец, диагональ и обратную диагональ.

2⃣Обработка запросов:
Для каждого запроса проверьте, освещена ли ячейка, используя словари строк, столбцов, диагоналей и обратных диагоналей.
После ответа на запрос выключите лампу в указанной ячейке и 8 соседних ячейках, обновив множества и словари.

3⃣Обновление состояний ламп:
Обновите состояния ламп и освещенных ячеек после каждого запроса, чтобы корректно обрабатывать следующие запросы.

😎 Решение:

public class Solution {
    public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
        var lamps_on = new HashSet<(int, int)>();
        var rows = new Dictionary<int, int>();
        var cols = new Dictionary<int, int>();
        var diag1 = new Dictionary<int, int>();
        var diag2 = new Dictionary<int, int>();

        foreach (var lamp in lamps) {
            int r = lamp[0], c = lamp[1];
            var key = (r, c);
            if (lamps_on.Contains(key)) continue;
            lamps_on.Add(key);
            if (!rows.ContainsKey(r)) rows[r] = 0;
            if (!cols.ContainsKey(c)) cols[c] = 0;
            if (!diag1.ContainsKey(r - c)) diag1[r - c] = 0;
            if (!diag2.ContainsKey(r + c)) diag2[r + c] = 0;
            rows[r]++;
            cols[c]++;
            diag1[r - c]++;
            diag2[r + c]++;
        }

        var directions = new (int, int)[] {(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)};
        var result = new int[queries.Length];

        for (int i = 0; i < queries.Length; i++) {
            int r = queries[i][0], c = queries[i][1];
            if (rows.ContainsKey(r) && rows[r] > 0 || cols.ContainsKey(c) && cols[c] > 0 || diag1.ContainsKey(r - c) && diag1[r - c] > 0 || diag2.ContainsKey(r + c) && diag2[r + c] > 0) {
                result[i] = 1;
            } else {
                result[i] = 0;
            }

            foreach (var dir in directions) {
                int nr = r + dir.Item1, nc = c + dir.Item2;
                var key = (nr, nc);
                if (lamps_on.Contains(key)) {
                    lamps_on.Remove(key);
                    rows[nr]--;
                    cols[nc]--;
                    diag1[nr - nc]--;
                    diag2[nr + nc]--;
                }
            }
        }

        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний