コード
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;
typedef signed long long ll;
#define ALL(a) (a.begin()), (a.end())
#define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end())
template <class T>
class CumulativeSum {
int ny, nx;
vector<vector<T>> sum;
public:
CumulativeSum(const vector<vector<T>>& a) {
ny = a.size();
nx = a[0].size();
sum.assign(ny + 1, vector<T>(nx + 1, 0));
for (int i = 0; i < ny; ++i) {
for (int j = 0; j < nx; ++j) {
sum[i + 1][j + 1] = a[i][j] + sum[i][j + 1] + sum[i + 1][j] - sum[i][j];
}
}
}
T getSum(int y1, int x1, int y2, int x2) {
if (y1 > y2 || x1 > x2) return 0;
y1 = max(y1, 0);
x1 = max(x1, 0);
y2 = min(y2, ny - 1);
x2 = min(x2, nx - 1);
return sum[y2 + 1][x2 + 1] - sum[y1][x2 + 1] - sum[y2 + 1][x1] +
sum[y1][x1];
}
};
int main() {
ios::sync_with_stdio(false);
int H, W;
cin >> H >> W;
vector<string> board(H);
for (int i = 0; i < H; ++i) {
cin >> board[i];
}
vector<vector<int>> right(H, vector<int>(W, 0));
vector<vector<int>> down(H, vector<int>(W, 0));
for (int h = 0; h < H; ++h) {
for (int w = 0; w < W; ++w) {
if (board[h][w] != '.') continue;
if (h < H - 1 && board[h + 1][w] == '.') down[h][w]++;
if (w < W - 1 && board[h][w + 1] == '.') right[h][w]++;
}
}
CumulativeSum<int> cs_down(down);
CumulativeSum<int> cs_right(right);
int Q;
cin >> Q;
for (int query = 0; query < Q; ++query) {
int r1, c1, r2, c2;
cin >> r1 >> c1 >> r2 >> c2;
r1--, c1--, r2--, c2--;
int ret = cs_down.getSum(r1, c1, r2, c2) + cs_right.getSum(r1, c1, r2, c2);
if (r2 < H - 1) ret -= cs_down.getSum(r2, c1, r2, c2);
if (c2 < W - 1) ret -= cs_right.getSum(r1, c2, r2, c2);
cout << ret << endl;
}
}
