#include #include //using namespace std; using namespace atcoder; //using mint = modint998244353; //const int mod = 998244353; //using mint = modint1000000007; //const int mod = 1000000007; 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; } template T binarySearch(T ok, T ng, const F &f) { while (abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (f(mid) ? ok : ng) = mid; } return ok; } #ifndef KWM_T_UTILITY_DIAGONAL_PREFIX_SUM_HPP #define KWM_T_UTILITY_DIAGONAL_PREFIX_SUM_HPP #include #include namespace kwm_t::utility { /** * @brief 斜め累積和(Diagonal Prefix Sum) * * 典型用途: * - 斜め方向(↘ / ↙)の区間和を高速に求める * - 斜め一直線上の部分列の和クエリ * - グリッド問題で「対角方向のみ」の集計 * * 計算量: * - 構築: O(HW) * - クエリ: O(1) * * @tparam T * 加算・減算が定義されている型(int, long long, double など) * * @param a * 元となる H×W の2次元配列 * * 制約 / 注意: * - 0-indexed * - クエリは半開区間: * diag_down : [ (x0,y0) → (x1-1,y1-1) ] * diag_up : [ (x0,y0) → (x1-1,y1+1) ] * - (x1-x0) == abs(y1-y0) を満たす必要がある(同一対角線) * * 使用例: * std::vector> a = { * {1, 2, 3}, * {4, 5, 6}, * {7, 8, 9} * }; * * kwm_t::utility::DiagonalPrefixSum dps(a); * * // ↘ 方向 (0,0) → (3,3) の対角和 = 1+5+9 = 15 * int x = dps.sum_down(0, 0, 3, 3); * * // ↙ 方向 (0,2) → (3,-1) の対角和 = 3+5+7 = 15 * int y = dps.sum_up(0, 2, 3, -1); * * verified: * - グリッド斜めクエリ系問題 */ template struct DiagonalPrefixSum { private: int h, w; std::vector> down; // ↘ std::vector> up; // ↙ public: DiagonalPrefixSum() = default; explicit DiagonalPrefixSum(const std::vector>& a) { build(a); } void build(const std::vector>& a) { h = (int)a.size(); w = h ? (int)a[0].size() : 0; down.assign(h + 1, std::vector(w + 1, T{})); up.assign(h + 1, std::vector(w + 1, T{})); // 初期値 for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { down[i + 1][j + 1] = a[i][j]; up[i + 1][j] = a[i][j]; } } // 累積 for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { down[i + 1][j + 1] += down[i][j]; up[i + 1][j] += up[i][j + 1]; } } } int height() const { return h; } int width() const { return w; } // ↘ 方向: (x0,y0) → (x1-1,y1-1) T sum_down(int x0, int y0, int x1, int y1) const { assert(0 <= x0 && x0 <= x1 && x1 <= h); assert(0 <= y0 && y0 <= y1 && y1 <= w); assert(x1 - x0 == y1 - y0); return down[x1][y1] - down[x0][y0]; } // ↙ 方向: (x0,y0) → (x1-1,y1+1) T sum_up(int x0, int y0, int x1, int y1) const { assert(0 <= x0 && x0 <= x1 && x1 <= h); assert(-1 <= y1 && y0 < w); assert(x1 - x0 == y0 - y1); return up[x1][y1 + 1] - up[x0][y0 + 1]; } }; } // namespace kwm_t::utility #endif // KWM_T_UTILITY_DIAGONAL_PREFIX_SUM_HPP #ifndef KWM_T_UTILITY_DIAGONAL_IMOS_HPP #define KWM_T_UTILITY_DIAGONAL_IMOS_HPP #include #include namespace kwm_t::utility { /** * @brief 斜めいもす法(Diagonal Imos) * * 典型用途: * - 斜め方向(↘ / ↙)への区間加算 * - 対角線上の区間に一括で値を加える * - 「斜めに影響が伝播する」グリッド問題 * * 計算量: * - 更新: O(1) * - 構築: O(HW) * - 取得: O(1) * * @tparam T * 加算・減算が定義されている型 * * 制約 / 注意: * - 0-indexed * - add は半開区間: * ↘ : (x0,y0) → (x1-1,y1-1) * ↙ : (x0,y0) → (x1-1,y1+1) * - (x1-x0) == abs(y1-y0) を満たす必要あり * - build() を呼ぶまで値は確定しない * * 使用例: * DiagonalImos imos(3, 3); * * // ↘ に +1 * imos.add_down(0, 0, 3, 3, 1); * * // ↙ に +2 * imos.add_up(0, 2, 3, -1, 2); * * imos.build(); * * int v = imos.get_down(1, 1); // 取得 * * verified: * - 斜め伝播系グリッド問題 */ template struct DiagonalImos { private: int h, w; std::vector> down; // ↘ std::vector> up; // ↙ public: DiagonalImos() = default; DiagonalImos(int h_, int w_) : h(h_), w(w_) { init(); } void init() { down.assign(h + 1, std::vector(w + 1, T{})); up.assign(h + 1, std::vector(w + 1, T{})); } int height() const { return h; } int width() const { return w; } // ↘ 方向: (x0,y0) → (x1-1,y1-1) void add_down(int x0, int y0, int x1, int y1, T val) { assert(x1 - x0 == y1 - y0); down[x0][y0] += val; down[x1][y1] -= val; } // ↙ 方向: (x0,y0) → (x1-1,y1+1) void add_up(int x0, int y0, int x1, int y1, T val) { assert(x1 - x0 == y0 - y1); up[x0][y0 + 1] += val; up[x1][y1 + 1] -= val; } void build() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { down[i + 1][j + 1] += down[i][j]; up[i + 1][j] += up[i][j + 1]; } } } // ↘ の値取得 T get_down(int i, int j) const { return down[i][j]; } // ↙ の値取得 T get_up(int i, int j) const { return up[i][j + 1]; } }; } // namespace kwm_t::utility #endif // KWM_T_UTILITY_DIAGONAL_IMOS_HPP int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int h, w; std::cin >> h >> w; std::vectors(h); rep(i, h)std::cin >> s[i]; std::vector b(h, std::vector(w)); rep(i, h)rep(j, w) { if ('#' == s[i][j])b[i][j] = 1; } // 斜め累積和 kwm_t::utility::DiagonalPrefixSum crossPrefixSum(b); // 斜めImos kwm_t::utility::DiagonalImos crossImos(h, w); rep(i, h)rep(j, w) { if ('.' == s[i][j])continue; auto f = [&](long long x)->bool { int y = x * 2 + 1; return crossPrefixSum.sum_down(i - x, j - x, i + x + 1, j + x + 1) >= y && crossPrefixSum.sum_up(i - x, j + x, i + x + 1, j - x - 1) >= y; }; int lim = std::min({ i,j,h - 1 - i,w - 1 - j }) + 1; auto get = binarySearch(0, lim, f); if (0 == get)continue; crossImos.add_down(i - get, j - get, i + get + 1, j + get + 1, 1); crossImos.add_up(i - get, j + get, i + get + 1, j - get - 1, 1); } crossImos.build(); bool chk = true; rep(i, h)rep(j, w) { if ('.' == s[i][j])continue; int cnt = crossImos.get_down(i, j) + crossImos.get_up(i, j); if (0 == cnt)chk = false; } std::cout << (chk ? "Yes" : "No") << std::endl; return 0; }