Problem C - Bacteria - periaのプログラム・メモ

問題

ルールを変更したライフゲームを行う．各マスについて

生きているマスについて，上と左が死んでいたらそのマスは死ぬ．
死んでいるマスについて，上と左が生きていたらそのマスは生まれる．

 *. → **    *@ → **
 .@ → *.    @. → *@

与えられた初期状態に対して，全滅までに何世代かかるか？

考え方

small だけ通すのでも構わなければシミュレーションで世代数を数えるのが楽かも．シミュレーションタイプのコードはこちら．コンパイルオプション -O は付けた方がいい．large の問題についてはメモリが 1TB とか必要になるので（計算時間外でも）アウト．

#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef pair<int,int> Point;
typedef pair<Point,Point> Rect;

int solve(void)
{
  int R;
  cin >> R;
  vector<Rect> rect;
  int x0 = 1000000, y0 = 1000000, x1 = 0, y1 = 0;
  for( int i = 0 ; i < R ; ++i ) {
    Point a, b;
    cin >> a.first >> a.second >> b.first >> b.second;
    rect.push_back(Rect(a, b));
    x0 = min(x0, a.first); y0 = min(y0, a.second);
    x1 = max(x1, b.first); y1 = max(y1, b.second);
  }
  // Move (x0,y0) -> (0,0)
  for( int i = 0 ; i < R ; ++i ) {
    rect[i].first.first   -= x0;
    rect[i].first.second  -= y0;
    rect[i].second.first  -= x0;
    rect[i].second.second -= y0;
  }

  // Initialize cells
  const int H = y1 - y0 + 1;
  const int W = x1 - x0 + 1;
  vector<string> bact(H, string(W, '.'));
  for( int i = 0 ; i < R ; ++i ) {
    for( int y = rect[i].first.second ; y <= rect[i].second.second ; ++y ) {
      for( int x = rect[i].first.first ; x <= rect[i].second.first ; ++x ) {
        bact[y][x] = '@';
      }
    }
  }

  // Count
  int  gen;
  bool cont = true;
  for( gen = 0 ; cont ; ++gen ) {
    cont = false;
    for( int y = H - 1 ; y >= 0 ; --y ) {
      for( int x = W - 1 ; x >= 0 ; --x ) {
        if( (x == 0 || bact[y][x-1] == '.') &&
            (y == 0 || bact[y-1][x] == '.') ) {
          bact[y][x] = '.';
        } else if( x > 0 && bact[y][x-1] == '@' &&
                   y > 0 && bact[y-1][x] == '@' ) {
          bact[y][x] = '@';
        }
        cont = cont || (bact[y][x] == '@');
      }
    }
  }

  return gen;
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cerr << "Case #" << t << "\n";
    cout << "Case #" << t << ": " << solve() << "\n";
  }
  return 0;
}

実際の所どう考えるかというと，小さな，簡単な形を考えるといい．まずは H×W の長方形１個．これが H+W-1 世代かかるのはすぐ分かるはず．
次は２つの長方形を組み合わせたパターンを考える．繋がらないパターン，辺がくっついたパターン，一部重複しているパターン．これを色々考察すると繋がったパターンでは，左上以外の死にマスは生きマスとして補完(#)できることがわかる．これをさらに「左と上が死んでるマス($)」と「右と下が死んでるマス(&)」とをつなぐ長方形に再分割し，その中で最長の世代数が繋がり全体の世代数になることが分かる．はず．(長方形2個じゃないけど)下記の例だと 9 世代かかる．

 ...@@..      ...@@##  再  .......    ...$@##
 ...@.@@  補  ...@#@@  分  .......    ...@#@@
 @@.@@@@  完  @@#@@@@  割  $@#@@@@ ＋ ...@@@@
 @@@@@..  →  @@@@@##  →  @@@@@##    ...@@##
 ..@@@..      ##@@@##      ##@@@#&    ...@@#&
                            9世代      8世代

さらに繋がる長方形が増えても基本的には同じで，繋がった全体に対しての (max(x_i), max(y_i)) が&になり，その繋がりを構成する長方形の左上座標を$として必要世代を計算すればいい．

アルゴリズム的には繋がったグループのクラスタリングが面倒かも？まぁ方法はどうあれそんなに計算量が大変になるってことは無いでしょう．

コード

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef pair<int,int> Point;
typedef pair<Point,Point> Rect;
typedef vector< set<Rect> > Cluster;

void connect(set<Rect>& cluster, vector<Rect>& rect,
             vector< vector<int> >& next, int st)
{
  vector<int> nxt = next[st];
  next[st].clear();
  vector<int>::iterator it;
  for( it = nxt.begin() ; it != nxt.end() ; ++it ) {
    cluster.insert(rect[*it]);
    connect(cluster, rect, next, *it);
  }
}

void isNext(Cluster& cluster, vector<Rect>& rect)
{
  bool ret = false;
  const int n = rect.size();
  vector< vector<int> > next(n);

  for( int i = 0 ; i < n ; ++i ) {
    const int i0x = rect[i].first.first,  i0y = rect[i].first.second;
    const int i1x = rect[i].second.first, i1y = rect[i].second.second;
    for( int j = i + 1 ; j < n ; ++j ) {
      const int j0x = rect[j].first.first,  j0y = rect[j].first.second;
      const int j1x = rect[j].second.first, j1y = rect[j].second.second;
      if( (i1x < j0x && i1y < j0y) || (i0x > j1x && i0y > j1y) ) continue;
      bool xIn = !((i1x + 1 < j0x) || (j1x + 1 < i0x));
      bool yIn = !((i1y + 1 < j0y) || (j1y + 1 < i0y));
      if( yIn && xIn ) {
        next[i].push_back(j);
        next[j].push_back(i);
      }
    }
  }

  for( int i = 0 ; i < n ; ++i ) {
    if( next[i].empty() ) { continue; }
    set<Rect> clust;
    clust.insert(rect[i]);
    connect(clust, rect, next, i);
    cluster.push_back(clust);
  }
}

int solve(void)
{
  int R;
  cin >> R;

  int ret = 0;
  vector<Rect> rects;
  for( int i = 0 ; i < R ; ++i ) {
    Rect r;
    cin >> r.first.first  >> r.first.second
        >> r.second.first >> r.second.second;
    rects.push_back(r);
    int w = r.second.first  - r.first.first + 1;
    int h = r.second.second - r.first.second + 1;
    ret = max(ret, w + h - 1);
  }

  Cluster cluster;
  isNext(cluster, rects);

  for( int i = 0 ; i < cluster.size() ; ++i ) {
    int x = 0, y = 0;
    set<Rect>::iterator p;
    for( p = cluster[i].begin() ; p != cluster[i].end() ; ++p ) {
      x = max(x, p->second.first);
      y = max(y, p->second.second);
    }
    for( p = cluster[i].begin() ; p != cluster[i].end() ; ++p ) {
      int w = x - p->first.first  + 1;
      int h = y - p->first.second + 1;
      ret = max(ret, w + h - 1);
    }
  }

  return ret;
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cerr << "Case #" << t << "\n";
    cout << "Case #" << t << ": " << solve() << "\n";
  }
  return 0;
}