結果

問題 No.179 塗り分け
ユーザー ramia777ramia777
提出日時 2022-05-18 17:58:59
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 28 ms / 3,000 ms
コード長 3,366 bytes
コンパイル時間 2,463 ms
コンパイル使用メモリ 83,628 KB
実行使用メモリ 4,376 KB
最終ジャッジ日時 2023-10-15 02:36:03
合計ジャッジ時間 4,716 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,372 KB
testcase_01 AC 2 ms
4,368 KB
testcase_02 AC 2 ms
4,372 KB
testcase_03 AC 2 ms
4,372 KB
testcase_04 AC 2 ms
4,368 KB
testcase_05 AC 7 ms
4,368 KB
testcase_06 AC 2 ms
4,372 KB
testcase_07 AC 2 ms
4,368 KB
testcase_08 AC 22 ms
4,372 KB
testcase_09 AC 22 ms
4,368 KB
testcase_10 AC 2 ms
4,372 KB
testcase_11 AC 1 ms
4,368 KB
testcase_12 AC 20 ms
4,372 KB
testcase_13 AC 2 ms
4,372 KB
testcase_14 AC 2 ms
4,372 KB
testcase_15 AC 2 ms
4,368 KB
testcase_16 AC 2 ms
4,368 KB
testcase_17 AC 2 ms
4,368 KB
testcase_18 AC 2 ms
4,372 KB
testcase_19 AC 2 ms
4,372 KB
testcase_20 AC 21 ms
4,372 KB
testcase_21 AC 24 ms
4,368 KB
testcase_22 AC 28 ms
4,372 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 22 ms
4,368 KB
testcase_25 AC 2 ms
4,372 KB
testcase_26 AC 5 ms
4,368 KB
testcase_27 AC 22 ms
4,372 KB
testcase_28 AC 2 ms
4,372 KB
testcase_29 AC 22 ms
4,368 KB
testcase_30 AC 10 ms
4,368 KB
testcase_31 AC 22 ms
4,372 KB
testcase_32 AC 8 ms
4,372 KB
testcase_33 AC 22 ms
4,372 KB
testcase_34 AC 6 ms
4,372 KB
testcase_35 AC 22 ms
4,368 KB
testcase_36 AC 2 ms
4,372 KB
testcase_37 AC 2 ms
4,368 KB
testcase_38 AC 2 ms
4,368 KB
testcase_39 AC 1 ms
4,368 KB
testcase_40 AC 2 ms
4,372 KB
testcase_41 AC 2 ms
4,368 KB
testcase_42 AC 2 ms
4,372 KB
testcase_43 AC 3 ms
4,368 KB
testcase_44 AC 7 ms
4,368 KB
testcase_45 AC 2 ms
4,372 KB
権限があれば一括ダウンロードができます

ソースコード

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