薔薇園の魔女 (AOJ 2310)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2310

問題

略

解法

レーザーを出す角度を使った平面走査で解く。答えが変わる角度はセルの右下の頂点を通る時であるのでそこをイベント点に突っ込む。各イベント点では同じ角度のイベント点を全て処理する。レーザーを通った直後にレーザーの右側で何個の連結成分があるかはUnionFindを使って計算可能。左側の部分は盤面をひっくり返してもう一度処理すれば良い。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct UnionFind {
  int parent[610 * 610];
  UnionFind() { MEMSET(parent, -1); }
  int UnionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) { return 0; }
    if (parent[x] > parent[y]) { swap(x, y); }
    parent[x] += parent[y];
    parent[y] = x;
    return 1;
  }
  int FindSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
};

typedef vector<int> Array;
typedef vector<Array> Matrix;

template <class T>
void PrintMatrix(const vector<vector<T> > &matrix) {
  REP(y, matrix.size()) {
    REP(x, matrix[y].size()) {
      cout << matrix[y][x] << " ";
    }
    puts("");
  }
}

template <class T>
vector<vector<T> > Transpose(const vector<vector<T> > &matrix) {
  int h = matrix.size();
  int w = matrix[0].size();
  vector<vector<T> > ret(w, vector<T>(h));
  REP(y, h) {
    REP(x, w) {
      ret[w - x - 1][h - y - 1] = matrix[y][x];
    }
  }
  return ret;
}

//=====================

UnionFind ufind;
pair<Matrix, Matrix> calc(const vector<vector<char> > &field) {
  int h = field.size();
  int w = field[0].size();
  ufind = UnionFind();
  pair<Matrix, Matrix> ret(Matrix(h, Array(w, 0)), Matrix(h, Array(w, 0)));
  map<double, vector<pair<int, int> > > que;
  REP(y, h - 1) {
    REP(x, w - 1) {
      int dy = h - 2 - y;
      int dx = x;
      if (dy == 0 && dx == 0) { continue; }
      int g = __gcd(dy, dx);
      dy /= g; dx /= g;
      double angle = dy / (double)dx;
      if (dx == 0) { angle = 1e+100; }
      que[angle].push_back(make_pair(x, y));
    }
  }
  int lans = 0;
  FORIT (it1, que) {
    //PrintMatrix(ret);
    //cout << endl;
    //cout << lans << endl;
    assert(lans >= 0);
    const vector<pair<int, int> > &poss = it1->second;
    FORIT(it2, poss) {
      ret.first[it2->second][it2->first] = lans;
    }
    FORIT(it2, poss) {
      int x = it2->first;
      int y = it2->second;
      if (field[y][x] == '.') { continue; }
      lans++;
      if (field[y + 1][x] == '#' && ufind.UnionSet(y * w + x, (y + 1) * w + x)) { lans--; }
      if (field[y][x + 1] == '#' && ufind.UnionSet(y * w + x, y * w + (x + 1))) { lans--; }
      if (field[y][x + 1] == '#' && field[y + 1][x] == '#' && ufind.UnionSet(y * w + x + 1, (y + 1) * w + x)) { lans--; }
      if (field[y][x] == '#' && field[y + 1][x + 1] == '#' && ufind.UnionSet(y * w + x, (y + 1) * w + x + 1)) { lans--; }
    }
    FORIT(it2, poss) {
      ret.second[it2->second][it2->first] = lans;
    }
  }
  return ret;
}

char str[1010];
int main() {
  int h, w;
  while (scanf("%d %d", &h, &w) > 0) {
    vector<vector<char> > field(h + 2, vector<char>(w + 2, '.'));
    REP(y, h) {
      int v = scanf("%s", str);
      assert(v == 1);
      REP(x, w) { field[y + 1][x + 1] = str[x]; }
    }
    pair<Matrix, Matrix> lans = calc(field);
    //PrintMatrix(lans.first);
    //PrintMatrix(lans.second);
    field = Transpose(field);
    pair<Matrix, Matrix> rans = calc(field);
    //PrintMatrix(rans.first);
    //PrintMatrix(rans.second);
    rans.first = Transpose(rans.first);
    rans.second = Transpose(rans.second);
    //PrintMatrix(rans);
    int ans = 0;
    REP(y, h + 1) {
      REP(x, w + 1) {
        ans = max(ans, lans.first[y][x] + rans.second[y + 1][x + 1]);
        ans = max(ans, lans.second[y][x] + rans.first[y + 1][x + 1]);
      }
    }
    printf("%d\n", ans);
  }
}