给你一个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; }
