結果

問題 No.179 塗り分け
ユーザー ramia777ramia777
提出日時 2022-05-18 17:58:59
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 9 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 27 ms
6,940 KB
testcase_09 AC 28 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 26 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 26 ms
6,944 KB
testcase_21 AC 29 ms
6,944 KB
testcase_22 AC 36 ms
6,944 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 28 ms
6,940 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 6 ms
6,940 KB
testcase_27 AC 28 ms
6,940 KB
testcase_28 AC 3 ms
6,944 KB
testcase_29 AC 28 ms
6,940 KB
testcase_30 AC 12 ms
6,940 KB
testcase_31 AC 28 ms
6,940 KB
testcase_32 AC 9 ms
6,944 KB
testcase_33 AC 28 ms
6,944 KB
testcase_34 AC 7 ms
6,944 KB
testcase_35 AC 29 ms
6,940 KB
testcase_36 AC 2 ms
6,940 KB
testcase_37 AC 2 ms
6,940 KB
testcase_38 AC 2 ms
6,944 KB
testcase_39 AC 2 ms
6,940 KB
testcase_40 AC 2 ms
6,944 KB
testcase_41 AC 2 ms
6,944 KB
testcase_42 AC 2 ms
6,944 KB
testcase_43 AC 4 ms
6,940 KB
testcase_44 AC 9 ms
6,940 KB
testcase_45 AC 3 ms
6,940 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