CF611C New Year and Domino

简介: CF611C New Year and Domino

给你一个h行w列的矩阵,‘.’表示空位,‘#’表示非空位,每次询问给出一个矩形左上顶点和右下顶点,问有多少种方案将一张1*21∗2的“骨牌”摆进这个子矩阵中(每个骨牌会覆盖相邻的两个空位)

输入样例#1:

5 8

…#…#

.#…

##.#…

##…#.##

4

1 1 2 3

4 1 4 1

1 2 4 5

2 5 5 8

输出样例#1:

4

0

10

15

思路:二位前缀和

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
int a[maxn][maxn];
int L[maxn][maxn], H[maxn][maxn], sum[maxn][maxn];
char str[maxn];
int main() {
  int n, m, q;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%s", str + 1);
    for (int j = 1; j <= m; j++) {
      if (str[j] == '.') a[i][j] = 1;
      L[i][j] = L[i][j - 1];
      H[i][j] = H[i - 1][j];
      if (a[i][j] && a[i - 1][j]) L[i][j]++;
      if (a[i][j] && a[i][j - 1]) H[i][j]++;
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (a[i][j] && a[i - 1][j]) + (a[i][j] && a[i][j - 1]);
    }
  }
  scanf("%d", &q);
  int x1, y1, x2, y2;
  while (q--) {
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    printf("%d\n", sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1] - L[x1][y2] + L[x1][y1 - 1] - H[x2][y1] + H[x1 - 1][y1]);
  }
  return 0;
}
相关文章