বাতি দ্বারা আলোকিত সমস্ত কোষের যোগফল খুঁজে পেতে C++ প্রোগ্রাম

ধরুন আমাদের একটি গ্রিড আছে যার সাথে H সারি এবং W কলাম রয়েছে। যেখানে প্রতিটি বর্গক্ষেত্র পরিপাটি বা অপরিচ্ছন্ন। আমরা এই গ্রিডে শূন্য বা তার বেশি পরিপাটি বর্গক্ষেত্রে বাতি রাখতে পারি। একটি বাতি চারটি দিকের কোষগুলিকে আলোকিত করতে পারে - উপরে, নীচে, বাম এবং ডানে - গ্রিডের একটি প্রান্তে বা একটি অপরিচ্ছন্ন বর্গক্ষেত্র প্রথমবার পৌঁছানোর ঠিক আগে পর্যন্ত (অপরিচ্ছন্ন কোষটি আলোকিত হবে না) ) বাতিটি যে ঘরের উপর স্থাপন করা হয়েছে সেটিকেও আলোকিত করবে। গ্রিডে G[i, j] হলে '.' সেই ঘরটি পরিপাটি এবং যখন এটি '#' হয় তখন এটি অপরিচ্ছন্ন। K কে পরিপাটি বর্গক্ষেত্রের সংখ্যা ধরা যাক। মোট ল্যাম্প স্থাপনের জন্য 2^K উপায় আছে। অনুমান করুন যে, এই 2^K উপায়গুলির প্রতিটির জন্য, এক বা একাধিক বাতি দ্বারা আলোকিত কোষের সংখ্যা গণনা করা হয়। আমাদের সেই সংখ্যাগুলোর যোগফল বের করতে হবে মডিউল 10^9 + 7।

সুতরাং, যদি ইনপুট মত হয়

।	।	#
#	।	।

তাহলে আউটপুট হবে 52

পদক্ষেপ

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

m := 10^9 + 7
N = 2003
Define 2D arrays u, l, r, d of order N x N, and another list p with N^2 elements.
h := row count of matrix
w := column count of matrix
tidy := 0
p[0] := 1
for initialize i := 1, when i <= h * w, update (increase i by 1), do:
   p[i] := p[i - 1] * 2 mod m
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      u[i, j] := i
      l[i, j] := j
      if i is non-zero, then:
         u[i, j] := u[i - 1, j]
      if j is non-zero, then:
         l[i, j] := l[i, j - 1]
      if matrix[i, j] is same as '#', then:
         u[i, j] := i + 1
         l[i, j] := j + 1
      Otherwise
         (increase tidy by 1)
for initialize i := h - 1, when i >= 0, update (decrease i by 1), do:
   for initialize j := w - 1, when j >= 0, update (decrease j by 1), do:
      d[i, j] := i
      r[i, j] := j
      if i < h - 1, then:
         d[i, j] := d[i + 1, j]
      if j < w - 1, then:
         r[i, j] := r[i, j + 1]
      if matrix[i, j] is same as '#', then:
         d[i, j] := i - 1
         r[i, j] := j - 1
cnt := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if matrix[i, j] is same as '#', then:
         Ignore following part, skip to the next iteration
      src := d[i, j] + r[i, j] - u[i, j] - l[i, j] + 1
      cnt := (cnt + (p[src] - 1) * p[tidy - src]) mod m
return cnt

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7, N = 2003;
int u[N][N], l[N][N], r[N][N], d[N][N], p[N * N];

int solve(vector<vector<char>> matrix){
   int h = matrix.size();
   int w = matrix[0].size();
   int tidy = 0;
   p[0] = 1;
   for (int i = 1; i <= h * w; ++i)
      p[i] = p[i - 1] * 2 % m;
   for (int i = 0; i < h; ++i){
      for (int j = 0; j < w; ++j){
         u[i][j] = i;
         l[i][j] = j;
         if (i)
            u[i][j] = u[i - 1][j];
         if (j)
            l[i][j] = l[i][j - 1];
         if (matrix[i][j] == '#'){
            u[i][j] = i + 1;
            l[i][j] = j + 1;
         }
         else
            ++tidy;
      }
   }
   for (int i = h - 1; i >= 0; --i){
      for (int j = w - 1; j >= 0; --j){
         d[i][j] = i;
         r[i][j] = j;
         if (i < h - 1)
            d[i][j] = d[i + 1][j];
         if (j < w - 1)
            r[i][j] = r[i][j + 1];
         if (matrix[i][j] == '#'){
            d[i][j] = i - 1;
            r[i][j] = j - 1;
         }
      }
   }
   int cnt = 0;
   for (int i = 0; i < h; ++i){
      for (int j = 0; j < w; ++j){
         if (matrix[i][j] == '#')
            continue;
         int src = d[i][j] + r[i][j] - u[i][j] - l[i][j] + 1;
         cnt = (cnt + (p[src] - 1) * p[tidy - src]) % m;
      }
   }
   return cnt;
}
int main(){
   vector<vector<char>> matrix = { { '.', '.', '#' }, { '#', '.', '.' } };
   cout << solve(matrix) << endl;
}

ইনপুট

3, 2, { 1, 5, 9 }, { 2, 4, 2 }