Chương trình C++ tính tổng số ô được đèn chiếu trong mọi cách đặt đèn

Lưới H x W, ô '.' (gọn) hoặc '#' (bẩn). Đặt đèn trên ô gọn. Đèn chiếu 4 hướng cho đến khi gặp biên hoặc ô bẩn. Có 2^K cách đặt đèn (K = số ô gọn). Tính tổng số ô được chiếu (ít nhất 1 đèn) trên tất cả các cách, modulo 1e9+7.

Ví dụ

Lưới 2x3 (xem hình), đầu ra 52.

Giải thuật

Tiền tính 4 mảng u,l,d,r: ô gọn gần nhất 4 hướng (kể cả chính nó). Số ô chiếu được từ ô (i,j) là src = d+r-u-l+1. Ô này được chiếu trong 2^K - 2^{K-src} cách đặt đèn (trừ cách không đặt đèn nào trong vùng chiếu). Tổng cộng sum (2^src - 1) * 2^{K-src}.

Mã 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) * 1LL * p[tidy - src]) % m;
        }
    }
    return cnt;
}

int main() {
    vector<vector<char>> matrix = { {'.','.','#'}, {'#','.','.'} };
    cout << solve(matrix) << endl;
}

Đầu vào / Đầu ra

Input: lưới 2x3
Output: 52