結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー moti
提出日時 2015-10-19 20:32:39
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,449 bytes
コンパイル時間 705 ms
コンパイル使用メモリ 102,068 KB
最終ジャッジ日時 2024-11-14 19:20:30
合計ジャッジ時間 1,229 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:38:11: error: ‘in_range’ function uses ‘auto’ type specifier without trailing return type
   38 | constexpr auto in_range(int x, int y) {
      |           ^~~~
main.cpp:38:11: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:42:1: error: ‘draw’ function uses ‘auto’ type specifier without trailing return type
   42 | auto draw(int x, int y, char c, char nc) {
      | ^~~~
main.cpp:42:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:60:1: error: ‘find_outer_land’ function uses ‘auto’ type specifier without trailing return type
   60 | auto find_outer_land() {
      | ^~~~
main.cpp:60:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:68:1: error: ‘make_tree’ function uses ‘auto’ type specifier without trailing return type
   68 | auto make_tree() {
      | ^~~~
main.cpp:68:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:133:1: error: ‘rec’ function uses ‘auto’ type specifier without trailing return type
  133 | auto rec(int curr, bool par_used = true) {
      | ^~~~
main.cpp:133:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <fstream>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

auto write_graph() -> void; // for Graphviz

constexpr int Max = 500000;  // 最小の輪の敷き詰めで、輪の個数が 110889

constexpr int   dx[] = {-1,0,1,0,-1,1,1,-1};
constexpr int   dy[] = {0,-1,0,1,-1,-1,1,1};
constexpr char  VisMark = ' ';
constexpr char  RingMark = 'o';

int N, M;
vector<string> in;
vector<int> tree[Max];

constexpr auto in_range(int x, int y) {
  return 0<=x&&x<M && 0<=y&&y<N;
}

auto draw(int x, int y, char c, char nc) {

  queue<pair<int, int>> q;
  q.emplace(x, y);
  while(!q.empty()) {
    auto p = q.front(); q.pop();
    int x = p.first, y = p.second;
    rep(i, 8) {
      int nx = x+dx[i], ny = y+dy[i];
      if(!in_range(nx, ny)) { continue; }
      if(in[ny][nx] != c) { continue; }
      in[ny][nx] = nc;
      q.emplace(nx, ny);
    }
  }

}

auto find_outer_land() {

  rep(i, N) { if(in[i][0] == '.') return make_pair(0, i); if(in[i][M-1] == '.') return make_pair(M-1, i); }
  rep(i, M) { if(in[0][i] == '.') return make_pair(i, 0); if(in[N-1][i] == '.') return make_pair(i, N-1); }

  assert(false);
}

auto make_tree() {

  queue<tuple<int, int, int>> nodeQ;
  // 外側の . をみつける
  auto outer_land = find_outer_land();
  int next_node = 0;
  nodeQ.emplace(outer_land.first, outer_land.second, next_node++);

  // BFS木を作るBFS
  while(!nodeQ.empty()) {
    auto const nodeQP = nodeQ.front(); nodeQ.pop();

    queue<pair<int, int>> q;
    q.emplace(get<0>(nodeQP), get<1>(nodeQP));
    in[get<1>(nodeQP)][get<0>(nodeQP)] = VisMark;
    vector<pair<int, int>> next_node_list;

    // 次の深さの輪を見つけるために、同じ深さの'.'を訪れるBFS
    while(!q.empty()) {
      auto const p = q.front(); q.pop();
      auto const x = get<0>(p), y = get<1>(p);
      rep(i, 8) {
        auto const nx = x+dx[i], ny = y+dy[i];
        if(!in_range(nx, ny)) { continue; }
        // '.' は訪れるだけ
        if(in[ny][nx] == '.') {
          if(i > 3 && in[y+dy[i-4]][x+dx[i-4]] != '.' && in[y+dy[(i-3)%4]][x+dx[(i-3)%4]] != '.') { continue; }
          in[ny][nx] = VisMark;
          q.emplace(nx, ny);
        }
        // 'x' は輪の要素なので、一つ見つけてあとは塗りつぶす
        if(in[ny][nx] == 'x') {
          draw(nx, ny, 'x', RingMark);
          next_node_list.emplace_back(nx, ny);
        }
      }
    }

    /*
    rep(i, N) cout << in[i] << endl;
    cout << "\n\n";
    */

    auto const node = get<2>(nodeQP);
    rep(i, next_node_list.size()) {
      tree[node].push_back(next_node);
//      add_edge(node, next_node);
      int x = next_node_list[i].first, y = next_node_list[i].second;
      rep(k, 8) {
        int nx = x+dx[k], ny = y+dy[k];
        if(!in_range(nx, ny)) { continue; }
        if(in[ny][nx] == '.') {
          nodeQ.emplace(nx, ny, next_node);
          break;
        }
      }
      next_node++;
    }
    
  }

}

int dp[Max][2];

auto rec(int curr, bool par_used = true) {

  int& ret = dp[curr][par_used];
  if(ret >= 0) { return ret; }

  if(tree[curr].empty()) {
    return ret = par_used ? 0 : 1;
  }

  if(par_used) {
    ret = 0;
    rep(i, tree[curr].size()) {
      int tar = tree[curr][i];
      ret += rec(tar, false);
    }
  }
  else {

    int r1 = 1;
    rep(i, tree[curr].size()) {
      int tar = tree[curr][i];
      r1 += rec(tar, true);
    }

    int r2 = 0;
    rep(i, tree[curr].size()) {
      int tar = tree[curr][i];
      r2 += rec(tar, false);
    }

    ret = max(r1, r2);
  }

  return ret;
}

auto main() -> signed {

  assert(cin >> N >> M);
  assert(1 <= N && N <= 1000);
  assert(1 <= M && M <= 1000);
  int ncnt = 0;
  for(string s; cin >> s; ncnt++) {
    in.push_back(s);
    assert(in[ncnt].size() == M);
  }
  assert(ncnt == N);

  rep(i, N) rep(j, M) assert(in[i][j] == '.' || in[i][j] == 'x');

  rep(i, N) {
    rep(j, M) {

      if(in[i][j] != 'x') { continue; }

      int xcount = 0;
      vector<pair<int, int>> xposlist;
      rep(k, 8) {
        int ni = i+dy[k], nj = j+dx[k];
        if(!in_range(nj, ni)) { continue; }
        xcount += in[ni][nj] == 'x';
        if(in[ni][nj] == 'x') xposlist.emplace_back(nj, ni);
      }
      if(xcount != 2) {
        cout << "xcount = " << xcount << endl;
        rep(i, xposlist.size()) {
          cout << xposlist[i].first << ", " << xposlist[i].second << endl;
        }
        assert(false && "xcount is not 2.");
      }
    }
  }


  make_tree();
  //write_graph();

  memset(dp, -1, sizeof dp);
  cout << rec(0) << endl;

  return 0;
}

/*
  Graphviz で木の画像を生成するコマンドを打つプログラム.
*/
auto write_graph() -> void {

  ofstream ofs("tree.dot");
  ofs << "digraph G {\n";
  rep(i, Max) {
    for(auto const& tar: tree[i]) {
      ofs << "  " << i << " -> " << tar << ";\n";
    }
  }
  ofs << "}\n";
  ofs.close();

  int ret, state;
  ret = system("dot -Tpng tree.dot > tree.png");
  if(WIFEXITED(ret)){
    state = WEXITSTATUS(ret);
  }
  else{
    state = -1;
  }
  printf("STATUS = %d\n", state);

//  exit(ret);
}
0