#1199252 (C++23) No.3806 Crossword Key with Cropping (Easy)

• 問題: No.3806 Crossword Key with Cropping (Easy)
• ユーザー: kwm_t
• 提出日時: 2026-11-14 16:48:04
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 681 ms / 2,000 ms
• コード長: 5,914 bytes
• コンパイル時間: 2,861 ms
• コンパイル使用メモリ: 358,116 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-11-14 16:48:28
• 合計ジャッジ時間: 22,345 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 53

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
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<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> 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 <vector>
#include <cassert>

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<std::vector<int>> a = {
 *       {1, 2, 3},
 *       {4, 5, 6},
 *       {7, 8, 9}
 *   };
 *
 *   kwm_t::utility::CumulativeSum2D<int> 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 <class T>
struct CumulativeSum2D {
private:
	std::vector<std::vector<T>> s;

	void build(const std::vector<std::vector<T>>& a) {
		int h = a.size();
		int w = h ? a[0].size() : 0;

		s.assign(h + 1, std::vector<T>(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<std::vector<T>>& 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<P> key_list(std::vector<string>s, 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<P>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;
	vector<string>s(h);
	rep(i, h)cin >> s[i];
	auto keys = key_list(s, 0);
	vector c(h, vector<int>(w));
	for (auto [x, y] : keys)c[x][y]++;
	kwm_t::utility::CumulativeSum2D<int> 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;
}