โปรแกรม 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 }

ผลลัพธ์

52