Fax画像は黒と白のピクセルが長方形状に並んだものである。
このまま送信するとデータ量が大きい為、以下の手順で圧縮する。
1. 各ピクセルについて、上のピクセルと同じ色ならS(same)、異なるならD(different)とマークする。(一行目の上には白のピクセルが有るものとして扱う)
2. 各ピクセルのマークを、一番上の行左から右、二行目左から右... とくっつけて、一つの文字列にする[SDDSDDSSSDDDSDD]
3. 文字列中のS, Dを、連続して繰り返された数+繰り返した文字に置き換える。[1S 2D 1S 2D 3S 3D 1S 2D]
4. SとDを取り除く。始まりがSかDかわからなくなると困るので、Dから始まる時は0を頭につける。[1 2 1 2 3 3 1 2]
Fax画像の横幅と、圧縮されたデータ列が与えられた時、Fax画像の黒色のピクセルの連結成分の数を答えよ。
ピクセルが連結しているとは、4辺のうちの1つが共有されていることである。
Fax画像の横幅wは10億以下、データ列中の数値の個数rは1000以下。
データ列中の数値は、10億以下。
解が10億以下である事は保障されている。
実際にシミュレーションを行うと、1000*10億個のピクセルを見ることになる為、破綻する。
入力のデータ列が1000までしか無い事を上手く使ってやる必要がある。
行の情報を、インデックス0からA-1までは黒、AからB-1までは白、BからC-1までは黒....と、区分にして持っておく。
一つのSの固まり、Dの固まりをどの様に加えても、区分は最高でも2つしか増えない為、一行に含まれる区分の数はO(r)で抑える事が出来る。
この情報を一行ずつ更新していき、黒の区分にIDを振り、上の行との連結を見て、Union Findのアルゴリズムを使うことにより、解を求める。
入ってくるデータが2行分以下のデータなら、上の行の区分を見ながらO(r)で、次の状態を生成できる。
2行分以上のSなら、丁度2n行分のデータは意味が無いので、2行分以下のSと等価。
データが2行分以上のDなら、丁度2n行分のデータを処理しても、最下列の状態は変わらず、中間の黒の連結成分の数は計算で求めることが出来る。
このように大きな固まりが来た時に特別処理をしてやる事で、1つのデータをO(r)で処理できる。
この方法を用いると、O(r^2)で連結成分の個数を計算出来る。
ただ、実装は重たい。