結果

問題 No.179 塗り分け
コンテスト
ユーザー ramia777
提出日時 2022-05-18 17:58:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 36 ms / 3,000 ms
コード長 3,366 bytes
コンパイル時間 792 ms
コンパイル使用メモリ 84,296 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-16 20:07:50
合計ジャッジ時間 2,617 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

// YukiCoder
//No.179 塗分け


//#include "stdafx.h"
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <cstring>

using namespace std;

#define W_MAX (50)
#define H_MAX (50)

vector<vector<int>> 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から始める(最小座標は１なので）
							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;
}
0