ABC 168 F - . (Single Dot)

• 問題
• AC

縦線と横線で分割される$(N+1)(M+1)$個くらいの矩形について、隣接している矩形との連結性を調べながらBFSすればよい……のだが、なかなか通らなかった。

$C_i = C_j$のような場合の扱いが問題だった。そういうケースがありえることは承知していて、間に面積0の矩形があると考えて問題ないと思っていたのだが、$(3, 1) - (5, 1), (4, 1) - (6, 1)$のように縦線が重なっている場合（$\Leftrightarrow A_i \le B_j \land A_j \le B_i$）に、前者の左にある矩形→中間の（面積0の）矩形→右の矩形、のように本来移動できないところを迂回して移動できてしまう可能性があることに気づいた。結局、前処理の時点でつながっている線分は1本につなげてしまうことで解決した。