結果

問題 No.348 カゴメカゴメ
ユーザー wing3196
提出日時 2016-02-27 00:30:26
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0