// YukiCoder //No.179 塗分け //#include "stdafx.h" #include #include #include #include #include #include #include #include #include using namespace std; #define W_MAX (50) #define H_MAX (50) vector> memo; typedef signed long long SLL; typedef unsigned long long ULL; int W, H; // 赤の座標(基準座標) x,y // 青の座標 x+dx, y+dy // 塗った個数     done_panel char _cell[152][152]; //元 char cell[152][152]; int x, y; int dx = 1, dy = 0; //並行移動距離 int blackPanelTotal = 0; int done_panel = 0; int main() { //有効範囲外は白で塗っておく for (y = 0; y < 152; y++) { for (x = 0; x < 152; x++) { cell[y][x] = '.'; _cell[y][x] = '.'; } } cin >> H; cin >> W; int first = 1; //H,Wは1~50が入力される、添え字としても1~50 for (y = 1; y <= H; y++) { for (x = 1; x <= W; x++) { cin >> cell[y+50][x+50]; _cell[y+50][x+50] = cell[y + 50][x + 50]; //黒のパネルの枚数を数えておく if (cell[y+50][x+50] == '#') { blackPanelTotal++; if (first) { first = 0; } } } } //黒パネルが2個未満ならすぐ終わる if (blackPanelTotal < 2) { cout << "NO" << endl; return 0; } dx = 1; dy = 0; while (1) { //塗れたパネルの数を初期化 done_panel = 0; //メモリのコピー memcpy(cell, _cell, 152*152); //2つ以上の黒パネルがあるなら最初の黒パネルから塗り始める for (y = 1; y <= H+50; y++) { for (x = 1; x <= W+50; x++) { //cout << "x=" << x-50 << ",y=" << y-50 << ",dx=" << dx << ",dy=" << dy << endl; //赤が塗れるとき if (cell[y][x] == '#') { //青も塗れていたら if(cell[y + dy][x + dx] == '#') { cell[y][x] = 'A'; cell[y + dy][x + dx] = 'B'; //塗れたパネルの数を更新 done_panel+=2; //cout << "painted: x=" << x - 50 << ",y=" << y - 50 << ",x+dx=" << x + dx - 50 << ",y+dy=" << y + dy - 50 << ",done=" << done_panel << ",Total=" << blackPanelTotal << endl; /* for (y = 1; y <= H; y++) { for (x = 1; x <= W; x++) { cout << cell[y + 50][x + 50]; } cout << endl; } */ //パネルの数が黒のパネルの数と等しくなったら終了 if (done_panel == blackPanelTotal) { cout << "YES" << endl; goto __COMPLETED; } } else { //青が塗れなかったら平行移動距離を次の候補に更新してもう一度最初からやり直す if (dx < W - 1) { dx++; } else { //最初の赤のX座標がWのときもあるので、Xの平行移動距離は-W+1から始める(最小座標は1なので) dx = -W + 1; if (dy < H - 1) { dy++; } else { //平行移動距離を使いつくしてしまった cout << "NO" << endl; goto __COMPLETED; } } goto __RETRY; } } } } __RETRY: ; } __COMPLETED: /* for (y = 1; y <= H; y++) { for (x = 1; x <= W; x++) { cout << cell[y + 50][x + 50]; } cout << endl; } getchar(); */ return 0; }