램프에 의해 밝아진 모든 셀의 합을 찾는 C++ 프로그램

<시간/>

H 행과 W 열이 있는 그리드가 있다고 가정합니다. 각 사각형이 깔끔하거나 어수선한 곳. 이 그리드에서 0개 이상의 깔끔한 사각형에 램프를 배치할 수 있습니다. 램프는 격자의 가장자리나 어수선한 사각형이 처음으로 도달하기 직전의 지점까지 위, 아래, 왼쪽, 오른쪽의 4방향 각각의 셀을 밝힐 수 있습니다. ). 램프는 램프가 놓여 있는 셀도 밝게 합니다. 그리드에서 G[i, j]가 '.'인 경우 그 셀은 깔끔한 것이고 '#'일 때는 어수선한 것입니다. K를 깔끔한 정사각형의 수라고 하자. 램프를 놓는 방법은 총 2^K입니다. 이러한 2^K 방식 각각에 대해 하나 이상의 램프에 의해 밝아진 셀의 수가 계산된다고 가정합니다. 우리는 모듈로 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 }