//形は複雑になり得るので、平行移動量を全探索しよう。 //平行移動を全探索すると…、一色を塗った時にもう一色をどこに塗るべきかが分かる //あ、そうそう…色はちゃんと区別しないとだめだから!むやみやたらに#を //片方の色で塗っていって、もう片方でも塗れるかとかやったらだめだから! //これはWA解かな?(貪欲に左上から赤で塗って、平行移動先を青で塗っている感じだけど) //って、マイナス方向!!'.'マスのみの時!!(泣 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int h, w; char s[50][52]; //#は濡れる bool trans(int i, int j) { int data[50][50] = {0}; int y, x; //cout << "i = " << i << " " << " j = " << j << endl; for( y = 0; y < h; y++ ) { for( x = 0; x < w; x++ ) { if ( s[y][x] == '#' && data[y][x] == 0 ) { if ( y + i < 0 || y + i >= h || x + j < 0 || x + j >= w ) { //cout << "WA1" << endl; return false; } if ( s[y+i][x+j] != '#' ) { //cout << "WA2" << endl; return false; } data[y][x]++; data[y+i][x+j]++; } } } for( y = 0; y < h; y++ ) { for( x = 0; x < w; x++ ) { if ( s[y][x] == '#' ) { if ( data[y][x] != 1 ) { //cout << "WA3" << endl; return false; } } } } return true; } signed main() { int i, j; cin >> h >> w; for( i = 0; i < h; i++ ) cin >> s[i]; int cnt = 0; for( i = 0; i < h; i++ ) for( j = 0; j < w; j++ ) cnt += ( s[i][j] == '#' ); if ( cnt == 0 || cnt%2 == 1 ) { cout << "NO" << endl; return 0; } for( i = 0; i < h; i++ ) { for( j = 0; j < w; j++ ) { if ( trans(i, j) || trans(-i, -j) || trans(-i, j) || trans(i, -j) ) { cout << "YES" << endl; return 0; } } } cout << "NO" << endl; return 0; }