問題文
縦 H マス,横 W マスの H×W マスからなるグリッドで表されるダンジョンがあります.
上から i 行目,左から j 列目のマス (i,j) は,Gi,j が #
のとき壁であり,.
のとき道です.
このダンジョンの主である MojaMoja 君は,次の条件を満たすように,1 組の 2 マスを結ぶワープホールを非負整数個設置します.
条件
- 任意の道のマスにいる人が,0 回以上の移動を繰り返すことによって,任意の道のマスへ到達することができる.
ここで,ある道のマス P にいる人が,ある道のマス Q へ移動できるとき,2 マス P,Q は以下の条件のうち 1 つ以上を満たします.
- P=:(i,j) とするとき,Q∈{(i+1,j),(i−1,j),(i,j+1),(i,j−1)}
- 1 組の 2 マス (P,Q) または (Q,P) を結ぶワープホールが存在する
MojaMoja 君が条件を満たすために,最小で何組のワープホールを設置する必要があるか,求めてください.
制約
- 1≤H,W≤2500
- Gi,j は
.
か #
のうちのいずれか (1≤i≤H,1≤j≤W)
入力
入力は以下の形式で標準入力から与えられる.
出力
答えを出力せよ.
サンプル
入力例1
4 5
#.##.
#..##
#####
#..##
たとえば,道のマスの組 ((2,3),(1,5)) を結ぶワープホールと,((2,2),(4,2)) を結ぶワープホールとを設置することで条件を満たします.
2 つ未満のワープホールによって目標を達成することはできないため,2
を出力します.
入力例2
4 5
#.#..
...##
.##..
#....