← Static tasks

1001. Grid Illumination

leetcode hard

#array#csharp#hard#hash-table#leetcode#matrix#string

Task

Имеется двумерная сетка размером 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]

C# solution

matched/original
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;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& GridIllumination(int n, int[][] lamps, int[][] queries) {
        var lamps_on = new HashSet<(int, int)>();
        var rows = new unordered_map<int, int>();
        var cols = new unordered_map<int, int>();
        var diag1 = new unordered_map<int, int>();
        var diag2 = new unordered_map<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.push_back(key);
            if (!rows.count(r)) rows[r] = 0;
            if (!cols.count(c)) cols[c] = 0;
            if (!diag1.count(r - c)) diag1[r - c] = 0;
            if (!diag2.count(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.size()];
        for (int i = 0; i < queries.size(); i++) {
            int r = queries[i][0], c = queries[i][1];
            if (rows.count(r) && rows[r] > 0 || cols.count(c) && cols[c] > 0 || diag1.count(r - c) && diag1[r - c] > 0 || diag2.count(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;
    }
}

Java solution

auto-draft, review before submit
import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
        var lamps_on = new HashSet<(int, int)>();
        var rows = new HashMap<int, int>();
        var cols = new HashMap<int, int>();
        var diag1 = new HashMap<int, int>();
        var diag2 = new HashMap<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;
    }
}

JavaScript solution

matched/original
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;
    }
}

Explanation

Algorithm

1⃣Инициализация данных:

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

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

2⃣Обработка запросов:

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

После ответа на запрос выключите лампу в указанной ячейке и 8 соседних ячейках, обновив множества и словари.

3⃣Обновление состояний ламп:

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

😎