Задача: 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⃣Обновление состояний ламп:
Обновите состояния ламп и освещенных ячеек после каждого запроса, чтобы корректно обрабатывать следующие запросы.

😎 Решение:

class Solution {
    gridIllumination(n, lamps, queries) {
        const lamps_on = new Set();
        const rows = new Map();
        const cols = new Map();
        const diag1 = new Map();
        const diag2 = new Map();

        for (const [r, c] of lamps) {
            const key = r * n + c;
            if (lamps_on.has(key)) continue;
            lamps_on.add(key);
            rows.set(r, (rows.get(r) || 0) + 1);
            cols.set(c, (cols.get(c) || 0) + 1);
            diag1.set(r - c, (diag1.get(r - c) || 0) + 1);
            diag2.set(r + c, (diag2.get(r + c) || 0) + 1);
        }

        const directions = [[0, 0], [0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]];
        const result = [];

        for (const [r, c] of queries) {
            if ((rows.get(r) || 0) > 0 || (cols.get(c) || 0) > 0 || (diag1.get(r - c) || 0) > 0 || (diag2.get(r + c) || 0) > 0) {
                result.push(1);
            } else {
                result.push(0);
            }

            for (const [dr, dc] of directions) {
                const nr = r + dr, nc = c + dc;
                const key = nr * n + nc;
                if (lamps_on.has(key)) {
                    lamps_on.delete(key);
                    rows.set(nr, rows.get(nr) - 1);
                    cols.set(nc, cols.get(nc) - 1);
                    diag1.set(nr - nc, diag1.get(nr - nc) - 1);
                    diag2.set(nr + nc, diag2.get(nr + nc) - 1);
                }
            }
        }

        return result;
    }
}

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