#83111 (C++11) No.348 カゴメカゴメ

提出ソース

結果

問題	No.348 カゴメカゴメ
ユーザー	moti
提出日時	2016-03-24 02:43:16
言語	C++11 (gcc 11.4.0)
結果	CE (最新) AC (最初)
実行時間	-
コード長	6,107 bytes
コンパイル時間	917 ms
コンパイル使用メモリ	106,652 KB
最終ジャッジ日時	2024-11-14 19:36:04
合計ジャッジ時間	1,706 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ

main.cpp:41:11: error: ‘in_range’ function uses ‘auto’ type specifier without trailing return type
   41 | constexpr auto in_range(int x, int y) {
      |           ^~~~
main.cpp:41:11: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:45:1: error: ‘draw’ function uses ‘auto’ type specifier without trailing return type
   45 | auto draw(int x, int y, char c, char nc) {
      | ^~~~
main.cpp:45:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:65:1: error: ‘find_outer_land’ function uses ‘auto’ type specifier without trailing return type
   65 | auto find_outer_land() {
      | ^~~~
main.cpp:65:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:73:1: error: ‘make_tree’ function uses ‘auto’ type specifier without trailing return type
   73 | auto make_tree() {
      | ^~~~
main.cpp:73:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:138:1: error: ‘rec’ function uses ‘auto’ type specifier without trailing return type
  138 | auto rec(int curr, bool par_used = true) {
      | ^~~~
main.cpp:138:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’

ソースコード

raw source code

// #57856 との違いはグリッドの入力をしたあと、グリッドの大きさを縦横+2したのみ。グリッドの端まで輪がかかっているとき、和を取りそこねていた。
// #83067 は実質同じコードだが、こちらのコードを少し綺麗に書きなおしたのが#83067のつもりです。
#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;
int node_cost[Max];
vector<int> tree[Max]; // to, cost

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) {

  int count = 0;
  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; }
      count++;
      in[ny][nx] = nc;
      q.emplace(nx, ny);
    }
  }
  return count;
}

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<tuple<int, 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') {
          auto xcount = draw(nx, ny, 'x', RingMark);
          next_node_list.emplace_back(nx, ny, xcount);
        }
      }
    }

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

    auto const node = get<2>(nodeQP);
    rep(i, next_node_list.size()) {
      auto x = get<0>(next_node_list[i]), y = get<1>(next_node_list[i]), next_node_cost = get<2>(next_node_list[i]);
      tree[node].emplace_back(next_node);
      node_cost[next_node] = next_node_cost;
      rep(k, 8) {
        auto 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 : node_cost[curr];
  }

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

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

    int r2 = 0;
    rep(i, tree[curr].size()) {
      auto 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);
  N += 2, M += 2;
  in.resize(N);
  in[0] = string(M, '.');
  REP(i, 1, N-1) {
    cin >> in[i];
    in[i] = "." + in[i] + ".";
  }
  in.back() = string(M, '.');

  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();

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

  return 0;
}

////////////////////////////////////////////////////////////////////////////////////////////
/*
  Verify用 1
  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);
}

yukicoder

結果

コンパイルメッセージ

ソースコード