#78624 (C++11) No.348 カゴメカゴメ

提出ソース

結果

問題	No.348 カゴメカゴメ
ユーザー	wing3196
提出日時	2016-02-27 00:30:26
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	2,751 bytes
コンパイル時間	1,658 ms
コンパイル使用メモリ	171,712 KB
実行使用メモリ	30,052 KB
最終ジャッジ日時	2024-09-24 10:45:45
合計ジャッジ時間	5,092 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	83 ms 20,328 KB
testcase_01	AC	7 ms 20,264 KB
testcase_02	AC	111 ms 30,052 KB
testcase_03	AC	81 ms 20,272 KB
testcase_04	AC	7 ms 20,120 KB
testcase_05	AC	7 ms 20,172 KB
testcase_06	AC	6 ms 20,220 KB
testcase_07	AC	7 ms 19,952 KB
testcase_08	AC	6 ms 20,168 KB
testcase_09	AC	7 ms 20,108 KB
testcase_10	AC	6 ms 20,268 KB
testcase_11	AC	6 ms 20,216 KB
testcase_12	AC	8 ms 20,164 KB
testcase_13	WA	-
testcase_14	AC	7 ms 20,224 KB
testcase_15	AC	86 ms 20,056 KB
testcase_16	AC	6 ms 20,160 KB
testcase_17	AC	7 ms 20,056 KB
testcase_18	AC	6 ms 20,088 KB
testcase_19	AC	6 ms 20,260 KB
testcase_20	AC	7 ms 20,156 KB
testcase_21	AC	6 ms 20,196 KB
testcase_22	AC	6 ms 20,120 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	AC	7 ms 20,048 KB
testcase_44	WA	-
testcase_45	AC	6 ms 20,280 KB
testcase_46	AC	6 ms 20,124 KB
testcase_47	WA	-
testcase_48	AC	7 ms 20,352 KB
testcase_49	WA	-
testcase_50	AC	6 ms 20,248 KB
testcase_51	AC	5 ms 20,056 KB
testcase_52	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int O = 1;

struct Point
{
	int x, y;
	Point() {}
	Point(int _x, int _y)
	{
		x = _x; y = _y;
	}
};

int cntID = 0;

struct Node
{
	int id;
	int p;
	vector<Node> child;
	Node(int _p)
	{
		p = _p; id = cntID++;
	}
};

int N, M;
char fld[1002][1002];
const int dx8[8] = {1, 1, 0, -1, -1, -1, -1, 0}, dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dx4[4] = {1, 0, -1, 0}, dy4[4] = {0, 1, 0, -1};

bool IsOutside(int x, int y)
{
	return x < -1 || M < x || y < -1 || N < y;
}

int PaintRing(int x, int y)
{
	int res = 0;
	queue<Point> q;
	q.push(Point(x, y));
	while (!q.empty())
	{
		Point f = q.front(); q.pop();
		if (fld[f.y + O][f.x + O] == '#') continue;
		fld[f.y + O][f.x + O] = '#';
		res++;
		for (int i = 0; i < 8; i++)
		{
			int nx = f.x + dx8[i], ny = f.y + dy8[i];
			if (IsOutside(nx, ny) || fld[ny + O][nx + O] != 'x') continue;
			q.push(Point(nx, ny));
		}
	}
	return res;
}

void CreateTree(Node &node, int x, int y)
{
	vector<pair<Point, int> > child;
	queue<Point> q;
	q.push(Point(x, y));
	while (!q.empty())
	{
		Point f = q.front(); q.pop();
		if (fld[f.y + O][f.x + O] == 'x')
		{
			int p = PaintRing(f.x, f.y);
			child.push_back(make_pair(Point(f.x, f.y), p));
			continue;
		}
		if (fld[f.y + O][f.x + O] == '#') continue;
		fld[f.y + O][f.x + O] = '#';
		for (int i = 0; i < 4; i++)
		{
			int nx = f.x + dx4[i], ny = f.y + dy4[i];
			if (IsOutside(nx, ny) || fld[ny + O][nx + O] == '#') continue;
			q.push(Point(nx, ny));
		}
	}
	/*for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			printf("%c", fld[i + O][j + O]);
		}
		puts("");
	}
	puts("");*/
	int res = 0;
	for (int i = 0; i < child.size(); i++)
	{
		
		for (int j = 0; j < 8; j++)
		{
			int nx = child[i].first.x + dx8[j], ny = child[i].first.y + dy8[j];
			if (IsOutside(nx, ny) || fld[ny + O][nx + O] != '.') continue;
			child[i].first = Point(nx, ny);
			break;
		}
		node.child.push_back(Node(child[i].second));
		CreateTree(node.child.back(), child[i].first.x, child[i].first.y);
	}
}

int memo[1000000][2];

int Solve(Node &node, bool b)
{
	if (memo[node.id][b] != -1) return memo[node.id][b];
	int res = 0;
	for (int i = 0; i < node.child.size(); i++)
	{
		int ma = Solve(node.child[i], false);
		if (!b) ma = max(ma, Solve(node.child[i], true) + node.child[i].p);
		res += ma;
	}
	return memo[node.id][b] = res;
}

signed main()
{
	fill((int*)memo, (int*)memo + 1000000*2, -1);
	fill((char*)fld, (char*)fld + 1002*1002, '.');
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> fld[i + O][j + O];
		}
	}
	Node root(0);
	CreateTree(root, -1, -1);
	printf("%lld\n", Solve(root, false));
	return 0;
}

yukicoder

結果

テストケース

ソースコード