Giả sử chúng ta có một lưới với H hàng và W cột. Nơi mỗi hình vuông là ngăn nắp hoặc không lộn xộn. Chúng ta có thể đặt đèn trên không hoặc nhiều ô vuông ngăn nắp hơn trong lưới này. Đèn có thể làm sáng các ô theo bốn hướng - lên, xuống, trái và phải - đến điểm ngay trước khi chạm tới một cạnh của lưới hoặc một hình vuông không gọn gàng lần đầu tiên (ô lộn xộn sẽ không được chiếu sáng ). Đèn cũng sẽ làm sáng ô mà nó được đặt trên đó. Trong lưới nếu G [i, j] là '.' ô đó gọn gàng và khi nó là '#' thì nó không gọn gàng. Gọi K là số ô vuông ngăn nắp. Tổng cộng có 2 ^ K cách đặt các đèn. Giả sử rằng, với mỗi cách trong số 2 ^ K cách này, số lượng ô được làm sáng bởi một hoặc nhiều đèn được tính. Chúng ta phải tìm tổng các số đó theo modulo 10 ^ 9 + 7.
Vì vậy, nếu đầu vào giống như
| . | . | # |
| # | . | . |
thì đầu ra sẽ là 52
Các bước
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
3, 2, { 1, 5, 9 }, { 2, 4, 2 } Đầu ra
52