โปรแกรม C++ หาผลรวมเซลล์ที่โคมไฟส่องสว่างทั้งหมดในกริด

คำอธิบายปัญหา

สมมติว่าเรามีกริด H แถว W คอลัมน์ เซลล์แต่ละช่องสะอาดหรือสกปรก สามารถวางโคมไฟบนเซลล์สะอาดได้ โคมไฟส่องสว่าง 4 ทิศทาง จนกว่าจะถึงขอบกริดหรือเซลล์สกปรก (เซลล์สกปรกไม่สว่าง) โคมยังส่องสว่างเซลล์ที่วางไว้ด้วย G[i,j] = '.' คือสะอาด '#' คือสกปรก ให้ K เป็นจำนวนเซลล์สะอาด มี 2^K วิธีวางโคม สำหรับแต่ละวิธี นับจำนวนเซลล์ที่สว่างโดยโคมอย่างน้อย 1 ดวง ต้องการผลรวมของตัวเลขเหล่านี้ mod 10^9+7

ตัวอย่าง: กริด 2x3 ตามตาราง ผลลัพธ์คือ 52

ขั้นตอนการแก้ปัญหา

m := 10^9 + 7
N := 2003
กำหนดอาร์เรย์ 2D u, l, r, d ขนาด N x N และลิสต์ p ขนาด N^2
h := จำนวนแถว, w := จำนวนคอลัมน์
tidy := 0
p[0] := 1
สำหรับ i := 1 ถึง h*w: p[i] := p[i-1] * 2 mod m
สำหรับ i := 0 ถึง h-1:
    สำหรับ j := 0 ถึง w-1:
        u[i,j] := i, l[i,j] := j
        ถ้า i > 0: u[i,j] := u[i-1,j]
        ถ้า j > 0: l[i,j] := l[i,j-1]
        ถ้า matrix[i,j] == '#': u[i,j] := i+1, l[i,j] := j+1
        มิฉะนั้น: เพิ่ม tidy ขึ้น 1
สำหรับ i := h-1 ถึง 0:
    สำหรับ j := w-1 ถึง 0:
        d[i,j] := i, r[i,j] := j
        ถ้า i < h-1: d[i,j] := d[i+1,j]
        ถ้า j < w-1: r[i,j] := r[i,j+1]
        ถ้า matrix[i,j] == '#': d[i,j] := i-1, r[i,j] := j-1
cnt := 0
สำหรับ i := 0 ถึง h-1:
    สำหรับ j := 0 ถึง w-1:
        ถ้า matrix[i,j] == '#': ข้าม
        src := d[i,j] + r[i,j] - u[i,j] - l[i,j] + 1
        cnt := (cnt + (p[src] - 1) * p[tidy - src]) mod m
คืนค่า cnt

ตัวอย่างโค้ด C++

#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