結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー しらっ亭
提出日時 2016-02-26 23:51:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,661 bytes
コンパイル時間 1,792 ms
コンパイル使用メモリ 180,724 KB
実行使用メモリ 19,912 KB
最終ジャッジ日時 2024-09-23 03:14:59
合計ジャッジ時間 8,254 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FORR(x,arr) for(auto&& x:arr)
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define ALL(x) (x).begin(), (x).end()
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
typedef long long ll;
// -------------------------------------

int N, M;
string G[1010];
bool used[1010][1010];
int sy, sx;
int lef, top, rig, bot;

typedef struct Ring {
  int top, lef, bot, rig, sz;
} Ring;

int DY[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int DX[8] = {0, 1, 0, -1, 1, -1, 1, -1};

int dfs(int y, int x) {
  bot = max(bot, y);
  rig = max(rig, x);
  top = min(top, y);
  lef = min(lef, x);
  used[y][x] = true;
  REP(d, 8) {
    int ny = y + DY[d];
    int nx = x + DX[d];
    if (ny < 0 || ny >= N) continue;
    if (nx < 0 || nx >= M) continue;
    if (G[ny][nx] == 'x' && !used[ny][nx]) {
      return dfs(ny, nx) + 1;
    }
  }
  return 1;
}

vector<Ring> rings;

int dfs2(int i, map<int, vector<int> >& con2, bool use) {
  Ring& r = rings[i];
  int ret1 = r.sz;
  int ret2 = 0;

  FORR(j, con2[i]) {
    ret2 += dfs2(j, con2, false);
  }

  if (!use) {
    FORR(j, con2[i]) {
      ret1 += dfs2(j, con2, true);
    }
    return max(ret1, ret2);
  }

  return ret2;
}

int main() {
  cin >> N >> M;
  REP(i, N) cin >> G[i];


  REP(y, N) {
    REP(x, M) {
      if (G[y][x] == 'x' && !used[y][x]) {
        top = bot = y;
        lef = rig = x;
        int sz = dfs(y, x);
        //_P("(%d,%d),(%d,%d), %d\n", top, lef, bot, rig, sz);
        rings.push_back({top, lef, bot, rig, sz});
      }
    }
  }

  int nr = SZ(rings);

  set<int> soto;
  REP(i, nr) {
    soto.insert(i);
  }

  map<int, int> con;
  REP(i, nr) REP(j, nr) {
    Ring& ri = rings[i];
    Ring& rj = rings[j];

    if (ri.top < rj.top && ri.lef < rj.lef && ri.rig > rj.rig && ri.bot > rj.bot) {
      // rj in ri
      soto.erase(j);
      if (con.find(j) == con.end()) {
        con[j] = i;
      }
      else {
        int pi = con[j];
        if (rings[pi].sz > rings[i].sz) {
          con[j] = i;
        }
      }
    }
  }

  map<int, vector<int> > con2;
  REP(i, nr) {
    if (con.find(i) != con.end()) {
      con2[con[i]].push_back(i);
    }
  }

  int ans = 0;
  FORR(i, soto) {
    //_P("soto: %d\n", i);
    ans += dfs2(i, con2, false);
  }

  cout << ans << endl;

  return 0;
}
0