結果
問題 | No.179 塗り分け |
ユーザー |
![]() |
提出日時 | 2015-04-06 00:17:53 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 9 ms / 3,000 ms |
コード長 | 2,033 bytes |
コンパイル時間 | 576 ms |
コンパイル使用メモリ | 81,328 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-23 14:25:42 |
合計ジャッジ時間 | 1,706 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 40 |
ソースコード
//形は複雑になり得るので、平行移動量を全探索しよう。 //平行移動を全探索すると…、一色を塗った時にもう一色をどこに塗るべきかが分かる //あ、そうそう…色はちゃんと区別しないとだめだから!むやみやたらに#を //片方の色で塗っていって、もう片方でも塗れるかとかやったらだめだから! //これはWA解かな?(貪欲に左上から赤で塗って、平行移動先を青で塗っている感じだけど) //って、マイナス方向!!'.'マスのみの時!!(泣 #include<iostream> #include<string> #include<algorithm> #include<functional> #include<vector> #include<cstdio> #include<cstring> #include<cstring> #include<cmath> #include<stack> #include<queue> #include<set> #include<map> 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; }