D - Dungeon Master

概要

基本的なアルゴリズムの実装を問う問題です．

問題原案：uni_kakurenbo

略解

$\max\,\{\,0,\,($通路マスの連結成分の個数$) - 1 \,\}$ が答えになることが示せます．
通路マスの連結成分の個数は BFS, DFS, Union-Find などを用いて求められます．

解説

$Ⅰ.$ 移動できるマスの言い換え

大雑把にいうと，「ある道のマスにいる人は，上下左右に隣接しているか，ワープホールによって結ばれている，他の道のマスへ移動することができる」となります．

$Ⅱ.$ グリッドの特徴

与えられるグリッドは，いくつかの，隣接したマスへの移動によって互いに行き来ができる $1$ つ以上の道のマスの集合に分割することができます．
以降これを部屋と呼びます．

つまり，設置したワープホールによって各部屋間を移動できるようにすればよいです．

※ . と # が逆でした．申し訳ございません

$Ⅲ.$ 設置すべきワープホール

同じ部屋に属するマス同士は既に互いに行き来することが可能なので，設置すべきワープホールは異なる部屋に属するマス同士を結ぶものに限ってよいです．
また，異なる部屋に属するマス同士であればどのマス同士を繋いでもよいです．

したがって，部屋の位置やマスの個数は重要でなく，「グリッド上に部屋がいくつ存在するか」のみが分かれば，最低限必要なワープホールの個数を求めることができます． これは，BFS, DFS, Union-Find などのアルゴリズムを用いることで，簡単に求まります．
(詳しい解説は他サイト様へ委ねます．基礎的かつとても有用なアルゴリズム・データ構造なので，知らなかった方はぜひ調べてみてください．)

「実装例」の項では BFS, Union-Find による解答の一例を紹介します．
再帰関数を用いて DFS を実装する場合はスタックオーバーフローなどのエラーに注意してください．

$O(N^2)$ や $O(\alpha(N^2)N^2)$ 時間で解けます．

$Ⅳ.$ 最低限必要なワープホールの個数

以上の議論から，この問題は「$N$ 個の部屋同士をワープホールで $2$ つずつ互いに繋いでいくとき，すべての部屋同士を(間接的に)繋げるためには最低で何組のワープホールが必要か？」という問題に帰着させることができます．
これは実際にいくつかの簡単な図を書いてみるとすぐにわかります．

結論は $N-1$ 個となりますが，これは数学的帰納法的に考えることで比較的簡単に確かめられます．

• 部屋の数が $1$ 個のとき，$0$ 組のワープホールで達成されます．
• 部屋の数が $2$ 個のとき，$1$ 組のワープホールによってそれらをつなげば，部屋の数が $1$ 個になったと見なせます．
• 部屋の数が $3$ 個のとき，$1$ 組のワープホールによってある $2$ つの部屋同士をつなげば，部屋の数が $2$ 個になったと見なせます．
• 部屋の数が $4$ 個のとき，$1$ 組のワープホールによってある $2$ つの部屋同士をつなげば，部屋の数が $3$ 個になったと見なせます．
• $\vdots$
• 部屋の数が $k$ 個のとき，$1$ 組のワープホールによってある $2$ つの部屋同士をつなげば，部屋の数が $k-1$ 個になったと見なせます．

$1$ 組のワープホールで，孤立した部屋の個数が $1$ ずつ減っていくと考えると，$N$ 個の部屋すべてを繋げる($1$ つにまとめる)のに必要なワープホールは最小で $N-1$ 組であるとわかります．

$Ⅴ.$ コーナーケース

グリッド上に道のマスが一つも存在しないときに注意してください．
部屋の個数が $0$ となりますが，答えは $-1$ ではありません．

このとき既に問題文中の条件は満たされているため，答えは $0$ となります．

$Ⅵ.$ グラフへの導入

この問題は，道のマスを頂点としたグラフ上で木を構築するために必要な残りの辺の本数を求めていることに違いありません．
(部屋は連結成分に当たります．)
「グラフ」や「木」といった用語が聞きなれない方はぜひ調べてみてください．

$Ⅶ.$ 発展

$1)$ 類題

• ACL Biginner Contest $\hspace{0.15em}$ C - Connect Cities
• ABC 269 $\hspace{0.15em}$ D - Do use hexagon grid
• POJ $\hspace{0.15em}$ No.2386 - Lake Counting
• AHC 013 $\hspace{0.15em}$ A - Server Room

実装例

$\\$

余談

またやってしまいました．
ACL Beginner Contest で既出でした．(「類題」のところにあります)
仕方ないので許してください☆
問題文作るのがかなり難しかったです．