#include #include #include using namespace std; void solve (int H, int W, vector& S) { // 場所からできるだけデカいバツを書いていったとき、同じになるか? enum direction { left_up, left_down, right_up, right_down, }; vector>> maximum_stretch(H, vector>(W, vector(4))); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '.') maximum_stretch[i][j][left_up] = -1; if (S[i][j] == '#') { if (i == 0 || j == 0) { maximum_stretch[i][j][left_up] = 0; } else { maximum_stretch[i][j][left_up] = maximum_stretch[i-1][j-1][left_up] + 1; } } } } for (int i = H-1; 0 <= i; i--) { for (int j = 0; j < W; j++) { if (S[i][j] == '.') maximum_stretch[i][j][left_down] = -1; if (S[i][j] == '#') { if (i == H-1 || j == 0) { maximum_stretch[i][j][left_down] = 0; } else { maximum_stretch[i][j][left_down] = maximum_stretch[i+1][j-1][left_down] + 1; } } } } for (int i = 0; i < H; i++) { for (int j = W-1; 0 <= j; j--) { if (S[i][j] == '.') maximum_stretch[i][j][right_up] = -1; if (S[i][j] == '#') { if (i == 0 || j == W-1) { maximum_stretch[i][j][right_up] = 0; } else { maximum_stretch[i][j][right_up] = maximum_stretch[i-1][j+1][right_up] + 1; } } } } for (int i = H-1; 0 <= i; i--) { for (int j = W-1; 0 <= j; j--) { if (S[i][j] == '.') maximum_stretch[i][j][right_down] = -1; if (S[i][j] == '#') { if (i == H-1 || j == W-1) { maximum_stretch[i][j][right_down] = 0; } else { maximum_stretch[i][j][right_down] = maximum_stretch[i+1][j+1][right_down] + 1; } } } } vector T(H, string(W, 0)); vector> draw_table(H, vector(W)); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) draw_table[i][j] = 0; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '.') T[i][j] = '.'; if (S[i][j] == '#') { int len = H*W; for (int k = 0; k < 4; k++) len = min(len, maximum_stretch[i][j][k]); if (len == 0) continue; draw_table[i-len][j-len] += 1; if (i+len+1 < H && j+len+1 < W) draw_table[i+len+1][j+len+1] += -1; } } } // 塗る for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) { if (0 < i && 0 < j) draw_table[i][j] += draw_table[i-1][j-1]; if (T[i][j] == '#') continue; if (0 < draw_table[i][j]) { T[i][j] = '#'; } else { T[i][j] = '.'; } } for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) draw_table[i][j] = 0; for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (S[i][j] == '.') T[i][j] = '.'; if (S[i][j] == '#') { int len = H*W; for (int k = 0; k < 4; k++) len = min(len, maximum_stretch[i][j][k]); if (len == 0) continue; draw_table[i+len][j-len] += 1; if (0 <= i-len-1 && j+len+1 < W) draw_table[i-len-1][j+len+1] += -1; } } } // 塗る for (int i = H-1; 0 <= i; i--) for (int j = 0; j < W; j++) { if (i < H-1 && 0 < j) draw_table[i][j] += draw_table[i+1][j-1]; if (T[i][j] == '#') continue; if (0 < draw_table[i][j]) { T[i][j] = '#'; } else { T[i][j] = '.'; } } bool ok = true; for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) if (S[i][j] != T[i][j]) ok = false; /* visualize for (int k = 0; k < 4; k++) { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cout << maximum_stretch[i][j][k] << " "; } cout << "\n"; } cout << "\n"; } for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { cout << T[i][j]; } cout << "\n"; } // */ if (ok) { cout << "Yes\n"; } else { cout << "No\n"; } } int main () { int H, W; cin >> H >> W; vector S(H); for (int i = 0; i < H; i++) cin >> S[i]; solve(H, W, S); }