[AtCoder] ABC 129 D – Lamp

問題

方針

行と列を分けて考える

グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで、列について考えます。\( c(i, j) = c(i, j+1) = . \) のとき、これらのマスは連結されているとします。連結されているマスが多ければその分マスを照らすことができます。同様にして、行についても同じことが言えます。

Union Find でマスの連結数を数える

グリッドのマスに対して一意に番号を振ります。\( i \) 行 \( j \) 列における番号 \( k \) を、\( k = W * i + j \) とします。横に隣接するマスがともに障害物でないとき、\( k \) と \( k + 1 \) は連結され、縦に隣接するマスがともに障害物でないとき、\( k \) と \( k + W \) は連結されます。ここで、注意する点は、行と列は分けて考えるので、行と列の二つの Union Find が必要になります。

ある番号 \( k \) の列の連結数を \( d_r(k) \)、行の連結数を \( d_c(k) \) とすると、そのマスに明かりを置いたときに照らすことができるマスの数は、\( d_r(k) + d_c(k) – 1\) となります。よって、全てのマスの値を求めて、最大値を求めます。

コード

提出したコード

類題

エイシング プログラミング コンテスト 2019 C – Alternating Path

解説