Score of Grid

　いろいろな解法があると思われますが、ここではUnionFindを用いて説明します。 UnionFindは二つの頂点が連結かないかを早い時間計算量で判断できるアルゴリズムです。本問題では、盤面をグラフとみなしたとき、多重辺、 自己ループが含まれますが、これらはスコアに影響を及びません。必要なのは、二つのマスが繋がれているか、いないかだけが重要です。

　盤面のグラフとしてのみなし方ですが、マス$(i, j)$を$i * W + j$番目の頂点と考えればよいです。

　よって、連結成分ごとにスコアを求めて、スコアの最大のもの、あるいはその次に大きいものとの和の最大値を答えることで、 正解することができます。

　計算量はUnionFindで$\mathcal{O}(\alpha(HW))$、最大のものを調べるためのソートの計算量で$\mathcal{O}(HWlog(HW))$から、 $\mathcal{O}(HWlog(HW))$で解けます。c++のsetなどを用いるときは、同じ数が統一され消えないよう注意してください。