ABC 401-500/ABC450C - Puddles - 競技プログラミング用 知識集積所

---

問題

ABC450C

必要知識

B以下レベルの内容は省略

• 深さ優先探索※または幅優先探索※

別解の場合

• UnionFind木※

考え方

行ける範囲全部に何かする、ということで、深さ優先探索※か幅優先探索※の出番。
特に、グリッド上の白マス連結成分数は、1つずつ白マスかどうかをチェックしていき、見つけ次第そこからつながる分を全部黒く塗っていく方法が典型。
しかしこの問題の場合は外周につながる分は数えないというのをどうするかが問題となる。

これは、探索順を変えることで解決する。
先に上下端と左右端を調査して、そこが白マスだった場合は結果としてカウントせずに連結部分を全て黒く塗る。
その後で改めて全体を調査して、今度はカウントしながら通常の方法を実行すればよい。

解答例

解答例

注意点

別解

UnionFind木※で解く

連結成分を扱うということで、UnionFind木※を用いることもできる。
h*w頂点にすると端の判定が難しいので、h*w+1マス用意して、追加の1マスを外周として扱う。
.groups()の返り値から外周に当たる1を引けば答えになる。
解答例