C++ प्रोग्राम लैंप द्वारा प्रकाशित सभी कोशिकाओं का योग ज्ञात करने के लिए

मान लीजिए कि हमारे पास एच पंक्तियों और डब्ल्यू कॉलम के साथ एक ग्रिड है। जहां हर चौक साफ-सुथरा हो। हम इस ग्रिड में शून्य या अधिक सुव्यवस्थित चौकों पर लैंप रख सकते हैं। एक दीपक चार दिशाओं में से प्रत्येक में कोशिकाओं को हल्का कर सकता है - ऊपर, नीचे, बाएँ और दाएँ - ग्रिड के किनारे से ठीक पहले या पहली बार एक गन्दा वर्ग तक पहुँचने से पहले (अस्वच्छ सेल को रोशन नहीं किया जाएगा) ) दीपक उस सेल को भी रोशन करेगा जिस पर इसे रखा गया है। ग्रिड में यदि G[i, j] '.' है। वह कोशिका सुव्यवस्थित होती है और जब वह '#' होती है तो वह अशुद्ध होती है। K को साफ-सुथरे वर्गों की संख्या होने दें। कुल मिलाकर लैंप लगाने के 2^के तरीके हैं। मान लें कि, इन 2^के तरीकों में से प्रत्येक के लिए, एक या अधिक लैंप द्वारा रोशन किए गए कक्षों की संख्या की गणना की जाती है। हमें उन संख्याओं का योग ज्ञात करना है मॉड्यूलो 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 }