結果

問題 No.179 塗り分け
ユーザー ramia777ramia777
提出日時 2022-05-18 16:55:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,200 bytes
コンパイル時間 861 ms
コンパイル使用メモリ 84,284 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-09-16 18:38:31
合計ジャッジ時間 5,492 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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 _x = 0;
int _y = 0;
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)
				{
					//最初のパネルの位置を記憶
					_x = x+50;
					_y = y+50;
					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 = _y; y <= H+50; y++)
		{
			for (x = _x; 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';
						//cout << "x=" << x  << ",y=" << y << ",x+dx=" << x + dx << ",y+dy=" << y + dy << endl;

						//塗れたパネルの数を更新
						done_panel+=2;

						//パネルの数が黒のパネルの数と等しくなったら終了
						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