結果

問題 No.348 カゴメカゴメ
ユーザー はまやんはまやんはまやんはまやん
提出日時 2017-04-22 13:01:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 390 ms / 2,000 ms
コード長 2,686 bytes
コンパイル時間 1,852 ms
コンパイル使用メモリ 184,208 KB
実行使用メモリ 25,724 KB
最終ジャッジ日時 2024-07-21 16:05:05
合計ジャッジ時間 6,171 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
int H, W; string G[1010];
//-----------------------------------------------------------------------------------
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int C[1010][1010];
vector<int> T, cnt;
vector<set<int>> E;
void makeTree() {
rep(y, 0, H) rep(x, 0, W) C[y][x] = -1;
int c = 0;
rep(y, 0, H) rep(x, 0, W) if (C[y][x] < 0) {
int d;
if (G[y][x] == '.') T.push_back(0), d = 2;
else T.push_back(1) , d = 1;
queue<int> que;
que.push(y * 1010 + x);
C[y][x] = c;
cnt.push_back(1);
while (!que.empty()) {
int q = que.front(); que.pop();
int xx = q % 1010;
int yy = q / 1010;
for (int i = 0; i < 8; i += d) {
int xxx = xx + dx[i];
int yyy = yy + dy[i];
if (xxx < 0 || W <= xxx) continue;
if (yyy < 0 || H <= yyy) continue;
if (G[y][x] != G[yyy][xxx]) continue;
if (0 <= C[yyy][xxx]) continue;
C[yyy][xxx] = c; cnt[c]++;
que.push(yyy * 1010 + xxx);
}
}
c++;
}
E.resize(c);
rep(y, 0, H) rep(x, 0, W) {
rep(i, 0, 4) {
int xx = x + dx[i * 2];
int yy = y + dy[i * 2];
if (xx < 0 || W <= xx) continue;
if (yy < 0 || H <= yy) continue;
if (C[yy][xx] == C[y][x]) continue;
int ca = C[y][x];
int cb = C[yy][xx];
E[ca].insert(cb);
E[cb].insert(ca);
}
}
}
//-----------------------------------------------------------------------------------
pair<int, int> dfs(int cu, int pa = -1) {
if (T[cu] == 0) { // ="."
int a = 0, b = 0;
for (int to : E[cu]) if (to != pa) {
auto p = dfs(to, cu);
a += max(p.second, p.first);
b += p.second;
}
return { a, b };
} else { // ="x"
int a = cnt[cu], b = 0;
for (int to : E[cu]) if (to != pa) {
auto p = dfs(to, cu);
a += p.second;
b += max(p.first, p.second);
}
return { a,b };
}
}
//-----------------------------------------------------------------------------------
int main() {
cin >> H >> W;
rep(y, 1, H + 1) cin >> G[y];
rep(x, 0, W + 2) G[0] += ".";
rep(y, 1, H + 1) G[y] = "." + G[y] + ".";
rep(x, 0, W + 2) G[H + 1] += ".";
W += 2; H += 2;
makeTree();
auto p = dfs(0);
int ans = max(p.first, p.second);
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0