#include //#include using namespace std; // using namespace atcoder; // using mint = modint1000000007; // const int mod = 1000000007; // using mint = modint998244353; // const int mod = 998244353; // const int INF = 1e9; // const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, n) for (int i = (n)-1; i >= 0; --i) #define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i) #define all(x) (x).begin(), (x).end() #define allR(x) (x).rbegin(), (x).rend() #define P pair template inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; } /** * @file cumulative_sum_2d.hpp * @brief 二次元累積和 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/utility/cumulative_sum_2d.hpp */ #ifndef KWM_T_UTILITY_CUMULATIVE_SUM_2D_HPP #define KWM_T_UTILITY_CUMULATIVE_SUM_2D_HPP #include #include namespace kwm_t::utility { /** * @brief 2次元累積和(2D Prefix Sum) * * 典型用途: * - グリッド上の長方形領域の総和を高速に求める * - 「部分矩形和クエリ」を大量に処理する問題 * - imos法や二次元DPの前処理 * * 計算量: * - 構築: O(HW) * - クエリ: O(1) * * @tparam T * 加算・減算が定義されている型(int, long long, double など) * * @param a * 元となる H×W の2次元配列 * * 制約 / 注意: * - 内部的に (H+1)×(W+1) の配列を持つ * - sum(x0, y0, x1, y1) は半開区間 [x0, x1) × [y0, y1) * - 0-indexed を前提とする * - a は長方形(各行のサイズが同じ)であること * * 使用例: * std::vector> a = { * {1, 2, 3}, * {4, 5, 6}, * {7, 8, 9} * }; * * kwm_t::utility::CumulativeSum2D cs(a); * * // (0,0) から (2,2) の和 → 1+2+4+5 = 12 * int res = cs.sum(0, 0, 2, 2); * * verified: * - https://atcoder.jp/contests/awc0048/submissions/74980601 */ template struct CumulativeSum2D { private: std::vector> s; void build(const std::vector>& a) { int h = a.size(); int w = h ? a[0].size() : 0; s.assign(h + 1, std::vector(w + 1, T{})); for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) s[i + 1][j + 1] = a[i][j]; for (int i = 0; i <= h; i++) for (int j = 0; j < w; j++) s[i][j + 1] += s[i][j]; for (int i = 0; i < h; i++) for (int j = 0; j <= w; j++) s[i + 1][j] += s[i][j]; } public: CumulativeSum2D() = default; explicit CumulativeSum2D(const std::vector>& a) { build(a); } int height() const { return (int)s.size() - 1; } int width() const { return s.empty() ? 0 : (int)s[0].size() - 1; } // [x0, x1) × [y0, y1) T sum(int x0, int y0, int x1, int y1) const { assert(0 <= x0 && x0 <= x1 && x1 <= height()); assert(0 <= y0 && y0 <= y1 && y1 <= width()); return s[x1][y1] - s[x1][y0] - s[x0][y1] + s[x0][y0]; } }; } // namespace kwm_t::utility #endif // KWM_T_UTILITY_CUMULATIVE_SUM_2D_HPP vector

key_list(std::vectors, int mode = 0) { int h = s.size(); int w = s[0].size(); auto keyData = [&](int i, int j)->P { int x = -1, y = -1; if (s[i][j] == '#')return { x,y }; // 横 if (j != w - 1 && s[i][j + 1] != '#' && (j == 0 || s[i][j - 1] == '#')) { x = 0; rep2(nj, j, w) { if (s[i][nj] == '#')break; x++; } } // 縦 if (i != h - 1 && s[i + 1][j] != '#' && (i == 0 || s[i - 1][j] == '#')) { y = 0; rep2(ni, i, h) { if (s[ni][j] == '#')break; y++; } } if (x == -1 && y == -1) { bool up = (i == 0 || s[i - 1][j] == '#'); bool down = (i == h - 1 || s[i + 1][j] == '#'); bool left = (j == 0 || s[i][j - 1] == '#'); bool right = (j == w - 1 || s[i][j + 1] == '#'); if (up && down && left && right) { x = 1; y = 1; } } return { x,y }; }; vector

ret; rep(i, h)rep(j, w) { auto key = keyData(i, j); if (key.first + key.second == -2)continue; if (mode == 0)ret.emplace_back(i, j); else ret.push_back(key); } return ret; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int h, w; cin >> h >> w; vectors(h); rep(i, h)cin >> s[i]; auto keys = key_list(s, 0); vector c(h, vector(w)); for (auto [x, y] : keys)c[x][y]++; kwm_t::utility::CumulativeSum2D cs(c); int q; cin >> q; while (q--) { int a, b, c, d; cin >> a >> b >> c >> d; a--, b--; int dx = c - a; int dy = d - b; int ans = 0; if (dx >= 3 && dy >= 3)ans += cs.sum(a + 1, b + 1, c - 1, d - 1); // 外周を頑張る auto f2 = [&](int x, int y)->bool { if (s[x][y] == '#')return false; // ue int cnt = 0; { bool chk0 = false; if (x == a)chk0 = true; if (x != a && s[x - 1][y] == '#')chk0 = true; if (chk0) { int x2 = x + 1, y2 = y; if (x2 < c && y2 < d && s[x2][y2] != '#')return true; else cnt++; } } // hidari { bool chk0 = false; if (y == b)chk0 = true; if (y != b && s[x][y - 1] == '#')chk0 = true; if (chk0) { int x2 = x, y2 = y + 1; if (x2 < c && y2 < d && s[x2][y2] != '#')return true; else cnt++; } } if (cnt == 2)return true; return false; }; auto f = [&](int x, int y)->bool { auto res = f2(x, y); return res; }; if (dx == 1) { ans = 0; rep2(j, b, d)ans += f(a, j); } else if (dy == 1) { ans = 0; rep2(i, a, c)ans += f(i, b); } else { rep2(j, b, d - 1)ans += f(a, j); rep2(i, a, c - 1)ans += f(i, d - 1); rep2(i, a + 1, c)ans += f(i, b); rep2(j, b + 1, d)ans += f(c - 1, j); } cout << ans << endl; } return 0; }