// 10_hand04.txt, 20_random01.txt, 20_random03.txt, 20_random05.txt, 20_random09.txt で, // WA版だったため, 再度, ロジック修正. // ※ すべて, NO と出力されていた. #include using namespace std; int main() { // 1. 入力情報取得. int H, W; cin >> H >> W; char c[H][W]; for(int i = 0; i < H; i++){ string s; cin >> s; for(int j = 0; j < W; j++) c[i][j] = s[j]; } // 2. '#' を カウント. int sharp = 0; for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) if(c[i][j] == '#') sharp++; // 2-1. '#' の 個数が, 奇数の場合. if(sharp % 2 != 0){ cout << "NO" << endl; return 0; } // 2-2. '#' の 個数が, 0個の場合(※ロジック追加). if(sharp == 0){ cout << "NO" << endl; return 0; } // 2-3. '#' の 個数が, 偶数の場合. // (仮称)青の領域で, 1点固定して, ベクトルを一つ固定し, 青の領域を全探索した結果, // すべて, ベクトル方向に, '#' であれば, 塗り分けが存在すると判定. // ベクトルを, 1つ固定. // ※負数のベクトルも考慮するためのロジック修正. string ans = "NO"; for(int vh = 1 - H; vh < H; vh++){ for(int vw = 1 - W; vw < W; vw++){ // ベクトル(0, 0) は, Skip. if(vh == 0 && vw == 0) continue; // 訪問したら, 1, 2 を セット. int memo[H][W] = {}; for(int h = 0; h < H; h++){ for(int w = 0; w < W; w++){ // ※境界条件を追加するためのロジック修正. int uh = h + vh; int uw = w + vw; if(uh < 0 || uw < 0 || uh >= H || uw >= W) continue; if(c[h][w] == '#' && memo[h][w] == 0 && c[uh][uw] == '#'){ memo[h][w] = 1; memo[uh][uw] = 2; } } } int one = 0, two = 0; for(int h = 0; h < H; h++){ for(int w = 0; w < W; w++){ if(memo[h][w] == 1) one++; if(memo[h][w] == 2) two++; } } // if(vh == -2 && vw == 3){ // for(int h = 0; h < H; h++){ // for(int w = 0; w < W; w++){ // cout << memo[h][w] << " "; // } // cout << endl; // } // } // 塗り分け の 存在チェック. if(one == sharp / 2 && two == sharp / 2){ ans = "YES"; break; } } } // 3. 出力. // ex. // [入力例] // 11 17 // .#.#.#.#......... // #.#.#.#.#..#..... // .#.#.#.#.##...... // ..#.#.#..##...... // ...#.#........... // ................. // ......#.#.#.#.... // .....#.#.#.#.#..# // ......#.#.#.#.##. // .......#.#.#..##. // ........#.#...... // // 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 // 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 // 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 // 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 // 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 // 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // 0 0 0 0 0 0 2 0 2 0 2 0 2 0 0 0 0 // 0 0 0 0 0 2 0 2 0 2 0 2 0 2 0 0 2 // 0 0 0 0 0 0 2 0 2 0 2 0 2 0 2 2 0 // 0 0 0 0 0 0 0 2 0 2 0 2 0 0 2 2 0 // 0 0 0 0 0 0 0 0 2 0 2 0 0 0 0 0 0 // YES // // [入力例] // 3 4 // ...# // .... // #... // // 0 0 0 2 // 0 0 0 0 // 1 0 0 0 // YES // // -> YES の はずだが, NO と出力された. // -> 10_hand04.txt, 20_random01.txt, 20_random03.txt, 20_random05.txt, 20_random09.txt で, WA版 // となった原因と推測される. // -> ベクトルとしては, (-2, 3) のはず. cout << ans << endl; return 0; }