ランプによって明るくなったすべてのセルの合計を見つけるC++プログラム

H行とW列のグリッドがあるとします。各正方形が整頓されているか整頓されていない場所。このグリッド内の0個以上の整頓された正方形にランプを配置できます。ランプは、セルを4つの方向（上、下、左、右）のそれぞれで、グリッドの端または乱雑な正方形に初めて到達する直前まで照らすことができます（乱雑なセルは点灯しません）。 ）。ランプはまた、それが置かれているセルを明るくします。グリッド内でG[i、j]が'。'の場合そのセルは整頓されており、「＃」の場合は整頓されていません。 Kを整頓された正方形の数とします。ランプを配置する方法は全部で2^Kあります。これらの2^Kの方法のそれぞれについて、1つまたは複数のランプによって照らされたセルの数が計算されると仮定します。 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