পাইথনে গ্রিড ইলুমিনেশন

ধরুন একটি N x N গ্রিড আছে, প্রতিটি সেল (x, y)-এ একটি ল্যাম্প আছে। প্রাথমিকভাবে কিছু ল্যাম্প অন রয়েছে। lamps[i] হল i-তম অন ল্যাম্পের লোকেশন। প্রতিটি অন ল্যাম্প তার x-অক্ষ, y-অক্ষ এবং দুটি ডায়াগোনালের সব স্কোয়ারকে আলোকিত করে। প্রতিটি কোয়েরি queries[i] = (x, y) এর জন্য, উত্তর হবে ১ যদি সেল (x, y) আলোকিত থাকে, অন্যথায় ০। প্রতিটি কোয়েরির পর (x, y) সেলে বা তার ৮-দিকের আশেপাশের যেকোনো ল্যাম্প বন্ধ করে দেওয়া হয়। উত্তরের একটি অ্যারে ফেরত দিন।

উদাহরণ: 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]++, y[j]++, diag1[i+j]++, diag2[i-j]++
• ans := খালি লিস্ট
• C-এ থাকা প্রতিটি মান i এর জন্য − a=i[0], b=i[1]; ans-এ ১ বা ০ যোগ করুন যাচাই করে x[a]+y[b]+diag1[a+b]+diag2[a-b] > 0 কিনা
• a-1 থেকে a+1 রো এবং b-1 থেকে b+1 কলামের জন্য − যদি (row, col) lamps-এ থাকে তবে সংশ্লিষ্ট কাউন্টার ডিক্রিমেন্ট করুন এবং lamps থেকে রিমুভ করুন
• 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]