পাইথনে গ্রিড আলোকসজ্জা

ধরুন আমাদের কোষের একটি N x N গ্রিড আছে, প্রতিটি ঘরে (x, y) একটি বাতি আছে। প্রাথমিকভাবে কিছু বাতি জ্বলছে। বাতি [i] হল i-th বাতির অবস্থান যা চালু আছে। প্রতিটি বাতি যেটি জ্বলছে তার x-অক্ষ, y-অক্ষ এবং উভয় কর্ণের প্রতিটি বর্গক্ষেত্রকে আলোকিত করে। এখন i-th ক্যোয়ারী অর্থাৎ queries[i] =(x, y), ক্যোয়ারীটির উত্তর হল 1 যদি ঘরটি (x, y) উজ্জ্বল হয়, অন্যথায় 0। প্রতিটি প্রশ্নের পরে (x, y), আমরা ঘরে (x, y) বা 8-দিকনির্দেশক সংলগ্ন যে কোনও বাতি বন্ধ করুন। উত্তরের একটি অ্যারে ফেরত দিন। প্রতিটি মানের উত্তর[i] i-th ক্যোয়ারী প্রশ্নের উত্তরের সমান হওয়া উচিত[i]।

সুতরাং, যদি ইনপুটটি N =5 এর মত হয়, ল্যাম্পগুলি হয় [[0,0],[4,4]], ক্যোয়ারী =[[1,1],[1,0]], তাহলে আউটপুট হবে [1] ,0]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ল্যাম্প :=প্রদত্ত অ্যারে ল্যাম্প থেকে জোড়ার সেট

• x, y, diag1, diag2

  মানচিত্র তৈরি করুন

• প্রতিটি জোড়ার জন্য (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

• উত্তর :=[]

• C

  -এ প্রতিটি মানের জন্য

  • a :=i[0], b :=i[1]

  • সন্নিবেশ করুন (1 যদি x[a] + y[b] + diag1[a + b] + diag2[a - b]> 0 অন্যথায় 0) ans

  • a - 1 থেকে a + 1

    রেঞ্জের সারির জন্য

    • b - 1 থেকে b + 1

      রেঞ্জে col এর জন্য

      • যদি সারি, কোল জোড়া ল্যাম্পে থাকে, তাহলে −

        • x[সারি] :=x[সারি] - 1

        • y[col] :=y[col] - 1

        • diag1[row + col] =diag1[সারি + কল] - 1

        • diag2[সারি - col] =diag2[সারি - কল] - 1

        • বাতি থেকে (সারি, কল) সরান

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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]