結果
| 問題 | No.348 カゴメカゴメ |
| ユーザー |
 wing3196
|
| 提出日時 | 2016-02-27 00:21:49 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,569 bytes |
| コンパイル時間 | 1,535 ms |
| コンパイル使用メモリ | 172,432 KB |
| 実行使用メモリ | 15,848 KB |
| 最終ジャッジ日時 | 2023-10-24 18:02:22 |
| 合計ジャッジ時間 | 8,212 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| 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 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
ソースコード
#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;
}
};
struct Node
{
int p;
vector<Node> child;
Node(int _p)
{
p = _p;
}
};
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 Solve(Node &node, bool 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 res;
}
signed main()
{
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;
}