実装のおおまかな方針

黒マスからなる領域を長方形の集合として管理することを考えます．ある長方形がもつマスの \(x\) 座標の最小値・最大値，\(y\) 座標の最小値・最大値によって，その長方形を表現できます．

ある \(1\) つの長方形に注目すると，\(1\) 回の大嵐によってこの領域は高々 \(2\) つの長方形に分割されます． したがって，\(N\) 回の大嵐が起きた後の黒マス領域は，高々 \(2^N\) 個の長方形領域として得られます． よって，\(P(N) = 2^N\) とおくと，\(N\) 回の大嵐が起きた後の長方形集合は \(O(N P(N))\) 時間で計算できます．

連結成分も長方形の集合として表せます．そこで，各長方形を「頂点」に対応付けたグラフで，辺で接している長方形のあいだに「辺」を張ったものを考えると，このグラフの連結成分がそのまま元のグリッドでの連結成分に対応します．

\(2\) つの長方形が辺で接しているかどうかの判定は \(O(1)\) でできるので，辺集合は \(O(P(N)^2)\) 時間で求まります．また，連結成分を求めるのは，深さ優先探索によって \(O(P(N)^2)\) 時間で，あるいは DSU を用いることで \(O(\alpha(P(N)) P(N)^2)\) 時間で可能です(\(\alpha(x)\) は DSU の計算量)．

以上より，\(O(P(N)^2) = O(4^N)\) 時間 でこの問題を解くことができ，十分高速です．

より高度な計算量解析

\(s\) 個以下の長方形領域からなり，同じ \(x\) 座標に存在する領域の個数の最大値が \(t\) 以下である領域を，\(j\) 回のタイプ X の大嵐で分割することを考えます．この結果として得られる領域は，ある整数 \(u\) (\(1 \leq u \leq t\)) に対して以下を満たします．

• \(s + uj\) 個以下の長方形領域からなり，同じ \(y\) 座標に存在する領域の個数の最大値が \(s-u+2j\) 以下である．

これを DP の形にして計算することで，\(N=14\) における長方形領域の個数は \(471\) 以下であることがわかります．

実装例 (C++)

実装例では DSU によって連結成分を求めています．

#include <iostream>
using std::cin;
using std::cout;
using std::min;
using std::max;
#include <vector>
using std::vector;
using std::pair;
#include <algorithm>
using std::sort;
#include <string>
using std::string;

typedef long long int ll;

#include <atcoder/dsu>
using atcoder::dsu;

ll n, h, w;
vector<string> c;
vector<ll> a, b;

typedef struct {
	ll xl;
	ll xr;
	ll yl;
	ll yr;
} Rect;

void solve () {
	vector<Rect> curr = {
		{0, h-1, 0, w-1}
	};

	for (ll qi = 0; qi < n; qi++) {
		vector<Rect> prev = curr;
		curr.clear();

		for (Rect r : prev) {
			if (c[qi] == "X") {
				if (r.xr < a[qi]) {
					curr.push_back({r.xl,  r.xr,    r.yl - b[qi], r.yr - b[qi]});
				} else if (r.xl >= a[qi]) {
					curr.push_back({r.xl,  r.xr,    r.yl + b[qi], r.yr + b[qi]});
				} else {
					curr.push_back({r.xl,  a[qi]-1, r.yl - b[qi], r.yr - b[qi]});
					curr.push_back({a[qi], r.xr,    r.yl + b[qi], r.yr + b[qi]});
				}
			} else if (c[qi] == "Y") {
				if (r.yr < a[qi]) {
					curr.push_back({r.xl - b[qi], r.xr - b[qi], r.yl,  r.yr});
				} else if (r.yl >= a[qi]) {
					curr.push_back({r.xl + b[qi], r.xr + b[qi], r.yl,  r.yr});
				} else {
					curr.push_back({r.xl - b[qi], r.xr - b[qi], r.yl,  a[qi]-1});
					curr.push_back({r.xl + b[qi], r.xr + b[qi], a[qi], r.yr});
				}
			} else {
				abort();
			}
		}
	}

	dsu d(curr.size());
	for (ll i = 0; i < curr.size(); i++) {
		for (ll j = i+1; j < curr.size(); j++) {
			Rect s = curr[i], t = curr[j];

			bool xtouch = (!(s.xr+1 <= t.xl) && !(t.xr+1 <= s.xl));
			bool ytouch = (!(s.yr+1 <= t.yl) && !(t.yr+1 <= s.yl));
			bool istouch = false;
			if ((s.xr+1 == t.xl) || (t.xr+1 == s.xl)) {
				if (ytouch) istouch = true;
			}
			if ((s.yr+1 == t.yl) || (t.yr+1 == s.yl)) {
				if (xtouch) istouch = true;
			}

			if (istouch) {
				d.merge(i, j);
			}
		}
	}
	vector<vector<int> > vs = d.groups();
	vector<ll> sizes(vs.size(), 0);
	for (ll i = 0; i < vs.size(); i++) {
		for (ll j = 0; j < vs[i].size(); j++) {
			Rect r = curr[vs[i][j]];
			ll area = (r.xr - r.xl + 1) * (r.yr - r.yl + 1);

			sizes[i] += area;
		}
	}
	
	sort(sizes.begin(), sizes.end());

	cout << sizes.size() << "\n";
	for (ll i = 0; i < sizes.size(); i++) {
		if (i > 0) cout << " ";
		cout << sizes[i];
	}
	cout << "\n";

	return;
}

int main (void) {
	
	cin >> n >> h >> w;
	
	c.resize(n);
	a.resize(n);
	b.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> c[i] >> a[i] >> b[i];
	}

	solve();
	

	return 0;
}