मान लीजिए हमारे पास N x N ग्रिड की कोशिकाएं हैं, प्रत्येक कोशिका (x, y) में एक लैंप है। प्रारंभ में, कुछ लैंप चालू हैं। lamps[i] i-वें लैंप का स्थान है जो चालू है। प्रत्येक चालू लैंप अपने x-अक्ष, y-अक्ष और दोनों विकर्णों पर हर वर्ग को चमकाता है। अब i-वें क्वेरी के लिए यानी queries[i] = (x, y), क्वेरी का उत्तर 1 है यदि कोशिका (x, y) चमक रही है, अन्यथा 0। प्रत्येक क्वेरी (x, y) के बाद, हम उन लैंप को बंद कर देते हैं जो कोशिका (x, y) पर हैं या 8-दिशात्मक रूप से आसन्न हैं। उत्तरों की एक सरणी लौटाएं। प्रत्येक मान answer[i] i-वें क्वेरी queries[i] के उत्तर के बराबर होना चाहिए।
इसलिए, यदि इनपुट इस तरह है N = 5, lamps हैं [[0,0],[4,4]], query = [[1,1],[1,0]], तो आउटपुट [1,0] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
lamps := दी गई सरणी lamps से जोड़ियों का सेट
मैप x, y, diag1, diag2 बनाएं
lamps में प्रत्येक जोड़ी (i, j) के लिए
x[i] := x[i] + 1, y[j] := y[j] + 1
diag1[i + j] := diag1[i + j] + 1, diag2[i - j] = diag2[i - j] + 1
ans := []
C में प्रत्येक मान i के लिए
a := i[0], b := i[1]
ans में डालें (1 यदि x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 अन्यथा 0)
row के लिए range a - 1 से a + 1 तक
col के लिए range b - 1 से b + 1 तक
यदि row, col जोड़ी lamps में है, तो −
x[row] := x[row] - 1
y[col] := y[col] - 1
diag1[row + col] = diag1[row + col] - 1
diag2[row - col] = diag2[row - col] - 1
lamps से (row, col) हटाएं
ans लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
from collections import defaultdict class Solution(object): def gridIllumination(self, N, b, C): lamps = {(i[0], i[1]) for i in b} x, y, diag1, diag2 = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int) for i, j in lamps: x[i] += 1 y[j] += 1 diag1[i + j] += 1 diag2[i - j] += 1 ans = [] for i in C: a = i[0] b = i[1] ans.append(1 if x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 else 0) for row in range( a - 1, a + 2): for col in range(b - 1, b + 2): if (row, col) in lamps: x[row] -= 1 y[col] -= 1 diag1[row + col] -= 1 diag2[row - col] -= 1 lamps.remove((row, col)) return ans ob = Solution() N = 5 lamps = [[0,0],[4,4]] query = [[1,1],[1,0]] print(ob.gridIllumination(N, lamps, query))इनपुट
5, [[0,0],[4,4]], [[1,1],[1,0]]
आउटपुट
[1, 0]