縦 マス,横 マスの マスからなるグリッドで表されるダンジョンがあります.
上から 行目,左から 列目のマス は, が #
のとき壁であり,.
のとき道です.
このダンジョンの主である MojaMoja 君は,次の条件を満たすように, 組の マスを結ぶワープホールを非負整数個設置します.
条件
ここで,ある道のマス にいる人が,ある道のマス へ移動できるとき, マス は以下の条件のうち つ以上を満たします.
MojaMoja 君が条件を満たすために,最小で何組のワープホールを設置する必要があるか,求めてください.
.
か #
のうちのいずれか 入力は以下の形式で標準入力から与えられる.
答えを出力せよ.
4 5 #.##. #..## ##### #..##
2
たとえば,道のマスの組 を結ぶワープホールと, を結ぶワープホールとを設置することで条件を満たします.
つ未満のワープホールによって目標を達成することはできないため,2
を出力します.
4 5 #.#.. ...## .##.. #....
2
2 4 #.#. .#.#
3