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

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

উদাহরণ

ইনপুট গ্রিড (চিত্রে দেখানো হয়েছে):
. . #
# . .
আউটপুট: 52

সমাধানের ধাপসমূহ

m := 10^9 + 7
N := 2003
u, l, r, d ২ডি অ্যারে (N x N), p লিস্ট (N^2 আকার)
h := ম্যাট্রিক্সের সারি, w := কলাম
tidy := 0
p[0] := 1
for i := 1 থেকে h*w: p[i] := p[i-1] * 2 mod m
for i := 0 থেকে h-1:
    for 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++

for i := h-1 থেকে 0:
    for 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
for i := 0 থেকে h-1:
    for j := 0 থেকে w-1:
        যদি matrix[i][j] == '#': continue
        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 }