#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; } template class CrossPrefixSum { // 斜め累積和 public: CrossPrefixSum(int h, int w, const std::vector> &org) :h(h), w(w) { init(org); } // 0:左上->1;右下(引数は閉区間) T getRui0(int i0, int j0, int i1, int j1) { return rui0[i1 + 1][j1 + 1] - rui0[i0][j0]; } // 0:右上→1;左下(引数は閉区間) T getRui1(int i0, int j0, int i1, int j1) { return rui1[i1 + 1][j1] - rui1[i0][j0 + 1]; }; private: int h, w; std::vector>rui0;//左上→右下 std::vector>rui1;//右上→左下 void init(const std::vector> &org) { rui0.assign(h + 1, std::vector(w + 1)); rui1.assign(h + 1, std::vector(w + 1)); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { rui0[i + 1][j + 1] = org[i][j]; rui1[i + 1][j + 0] = org[i][j]; } } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { rui0[i + 1][j + 1] += rui0[i + 0][j + 0]; rui1[i + 1][j + 0] += rui1[i + 0][j + 1]; } } } }; template class CrossImos { // 斜めimos public: CrossImos(int h, int w) :h(h), w(w) { init(); } void init() { imos0.assign(h + 1, std::vector(w + 1)); imos1.assign(h + 1, std::vector(w + 1)); } // 0:左上->1;右下(引数は閉区間) void add0(int i0, int j0, int i1, int j1, T val) { imos0[i0 + 0][j0 + 0] += val; imos0[i1 + 1][j1 + 1] -= val; } // 0:右上→1;左下(引数は閉区間) void add1(int i0, int j0, int i1, int j1, T val) { imos1[i0 + 0][j0 + 1] += val; imos1[i1 + 1][j1 + 0] -= val; } T get0(int i, int j) { return imos0[i][j]; } T get1(int i, int j) { return imos1[i][j + 1]; } void build() { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { imos0[i + 1][j + 1] += imos0[i + 0][j + 0]; imos1[i + 1][j + 0] += imos1[i + 0][j + 1]; } } } void dump() { for (int i = 0; i < h + 1; ++i) { for (int j = 0; j < w + 1; ++j) { std::cout << imos0[i][j] << " "; } std::cout << std::endl; } std::cout << std::endl; for (int i = 0; i < h + 1; ++i) { for (int j = 0; j < w + 1; ++j) { std::cout << imos1[i][j] << " "; } std::cout << std::endl; } }; private: int h, w; std::vector>imos0;//左上→右下 std::vector>imos1;//右上→左下 }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin >> h >> w; vectors(h); rep(i, h)cin >> s[i]; vector b(h, vector(w)); rep(i, h)rep(j, w) { if ('#' == s[i][j])b[i][j] = 1; } // 斜め累積和 auto crossPrefixSum = CrossPrefixSum(h, w, b); // 斜めImos auto crossImos = CrossImos(h, w); vector cnt(h, vector(w)); rep(i, h)rep(j, w) { if ('.' == s[i][j])continue; auto f = [&](long long x)->bool { int y = x * 2 + 1; { int i0 = i - x; int j0 = j - x; int i1 = i + x; int j1 = j + x; int cnt = crossPrefixSum.getRui0(i0, j0, i1, j1); if (cnt < y)return false; } { int i0 = i - x; int j0 = j + x; int i1 = i + x; int j1 = j - x; int cnt = crossPrefixSum.getRui1(i0, j0, i1, j1); if (cnt < y)return false; } return true; }; int lim = min({ i,j,h - 1 - i,w - 1 - j }) + 1; auto get = binarySearch(0, lim, f); if (0 == get)continue; crossImos.add0(i - get, j - get, i + get, j + get, 1); crossImos.add1(i - get, j + get, i + get, j - get, 1); } crossImos.build(); bool chk = true; rep(i, h)rep(j, w) { if ('.' == s[i][j])continue; int cnt = crossImos.get0(i, j) + crossImos.get1(i, j); if (0 == cnt)chk = false; } cout << (chk ? "Yes" : "No") << endl; return 0; }