結果
問題 | 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 |
ソースコード
#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;}