/* -*- coding: utf-8 -*- * * 2641.cc: No.2641 draw X - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_HW = 1000000; /* typedef */ typedef vector vi; typedef vector vvi; /* global variables */ char s[MAX_HW + 4], t[MAX_HW + 4]; /* subroutines */ /* main */ int main() { int h, w; scanf("%d%d", &h, &w); int hw = h * w; for (int i = 0; i < h; i++) scanf("%s", s + i * w); int m = h + w - 1; vvi ls0(m, vi(w, -1)), rs0(m, vi(w, -1)); vvi ls1(m, vi(w, -1)), rs1(m, vi(w, -1)); for (int i = 0; i < m; i++) { int x0 = max(0, i - (h - 1)), x1 = min(w - 1, i) + 1; // y + x = i -> y = i - x for (int r = x0; r < x1;) { while (r < x1 && s[(i - r) * w + r] == '.') r++; if (r >= x1) break; int l = r; while (r < x1 && s[(i - r) * w + r] == '#') r++; for (int x = l; x < r; x++) ls0[i][x] = l, rs0[i][x] = r - 1; } // (h - 1 - y) + x = i -> y = (h - 1) - (i - x) for (int r = x0; r < x1;) { while (r < x1 && s[(h - 1 - (i - r)) * w + r] == '.') r++; if (r >= x1) break; int l = r; while (r < x1 && s[(h - 1 - (i - r)) * w + r] == '#') r++; for (int x = l; x < r; x++) ls1[i][x] = l, rs1[i][x] = r - 1; } } vvi cs0(m, vi(w + 1, 0)), cs1(m, vi(w + 1, 0)); for (int y = 1; y < h - 1; y++) for (int x = 1; x < w - 1; x++) if (s[y * w + x] == '#') { int i0 = y + x, i1 = (h - 1 - y) + x; int r = min(min(x - ls0[i0][x], rs0[i0][x] - x), min(x - ls1[i1][x], rs1[i1][x] - x)); if (r > 0) { cs0[i0][x - r]++, cs0[i0][x + r + 1]--; cs1[i1][x - r]++, cs1[i1][x + r + 1]--; } } fill(t, t + hw, '.'); for (int i = 0; i < m; i++) { for (int x = 0; x < w; x++) { if (cs0[i][x] > 0) t[(i - x) * w + x] = '#'; cs0[i][x + 1] += cs0[i][x]; } for (int x = 0; x < w; x++) { if (cs1[i][x] > 0) t[(h - 1 - (i - x)) * w + x] = '#'; cs1[i][x + 1] += cs1[i][x]; } } for (int i = 0; i < hw; i++) if (s[i] != t[i]) { puts("No"); return 0; } puts("Yes"); return 0; }