問題文
ある王国の領土は、縦 行、横 列のグリッドで表されます。上から 行目、左から 列目のマスをマス と呼びます。
各マスは陸地か海のどちらかです。 の 文字目が # のときマス は陸地であり、. のとき海です。
陸地のマスからは、上下左右に隣接する陸地のマスへ移動できます。互いに移動し合える陸地のマス全体を、ひとつの 島 と呼びます。現在、王国には 個の島があります。
国王は、すべての島を合併してひとつの島にまとめる政策を打ち出しました。王国は次の 2 種類の工事を、好きな順番で何度でも行えます。
- 海のマスを 1 つ選んで埋め立て、陸地にする。
- 陸地のマスを 1 つ選んで掘削し、海にする。
工事は 1 回あたり費用が かかります。島の個数をちょうど 個にするために必要な費用の最小値を求めてください。
制約
- は整数
- は
#と.からなる長さ の文字列 - 与えられるグリッドの島の個数は 個である
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
サンプル 1
入力
2 5 2
##.##
##.##
出力
1
マス を埋め立てると、 つの島が つになります。
サンプル 2
入力
3 6 2
##....
......
...###
出力
2
左上の マスの島を掘削するのが最善です。
サンプル 3
入力
9 9 4
....#....
....#....
....#....
.........
###...###
.........
....#....
....#....
....#....
出力
5
サンプル 4
入力
8 12 7
.###...#...#
..#..###...#
#.#...###...
...#....#...
....#..##.##
..#.#####...
.##..##.#...
##..###.#...
出力
7
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする