結果

問題 No.348 カゴメカゴメ
ユーザー しらっ亭しらっ亭
提出日時 2016-02-27 00:15:18
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,997 bytes
コンパイル時間 1,991 ms
コンパイル使用メモリ 192,308 KB
実行使用メモリ 18,024 KB
最終ジャッジ日時 2023-10-24 18:01:54
合計ジャッジ時間 5,766 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
10,984 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 TLE -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
typedef pair<int, bool> IB;
map<IB, int> memo;
map<int, vector<int> > con2;

int dfs2(int i, bool use) {
  IB key = {i, use};
  if (memo.find(key) != memo.end()) return memo[key];

  Ring& r = rings[i];
  int ret1 = r.sz;
  int ret2 = 0;

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

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

  return memo[key] = 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);
  }

  sort(ALL(rings), [](const Ring& a, const Ring& b) {
      return a.top != b.top ? a.top < b.top
      : a.lef != b.lef ? a.lef < b.lef
      : a.bot != b.bot ? a.bot < b.bot
      : a.rig < b.rig;} );

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

    if (ri.sz < 14) continue;

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

  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, false);
  }

  cout << ans << endl;

  return 0;
}
0