難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) 未投票 (0票)

投票の分布

まだ投票はありません。

  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.50票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Merge the Islands

作成者 yura1685

難易度(作成者設定) Lv.7

難易度(投票) 未投票 (0票)

実行時間制限
2 秒
メモリ制限
512 MiB

問題文

ある王国の領土は、縦 HH 行、横 WW 列のグリッドで表されます。上から ii 行目、左から jj 列目のマスをマス (i,j)(i, j) と呼びます。

各マスは陸地か海のどちらかです。SiS_i の jj 文字目が # のときマス (i,j)(i, j) は陸地であり、. のとき海です。

陸地のマスからは、上下左右に隣接する陸地のマスへ移動できます。互いに移動し合える陸地のマス全体を、ひとつの 島 と呼びます。現在、王国には KK 個の島があります。

国王は、すべての島を合併してひとつの島にまとめる政策を打ち出しました。王国は次の 2 種類の工事を、好きな順番で何度でも行えます。

  • 海のマスを 1 つ選んで埋め立て、陸地にする。
  • 陸地のマスを 1 つ選んで掘削し、海にする。

工事は 1 回あたり費用が 11 かかります。島の個数をちょうど 11 個にするために必要な費用の最小値を求めてください。

制約

  • 1≤H,W1\le H, W
  • H×W≤104H\times W \leq 10^4
  • 2≤K≤7\color{red}2 \leq K \leq 7
  • H,W,KH, W, K は整数
  • SiS_i は # と . からなる長さ WW の文字列
  • 与えられるグリッドの島の個数は KK 個である

入力

入力は以下の形式で標準入力から与えられる。

HH WW KK S1S_1 S2S_2 ⋮\vdots SHS_H

出力

答えを出力せよ。


サンプル 1

入力

2 5 2
##.##
##.##

出力

1

マス (1,3)(1, 3) を埋め立てると、22 つの島が 11 つになります。

サンプル 2

入力

3 6 2
##....
......
...###

出力

2

左上の 22 マスの島を掘削するのが最善です。

サンプル 3

入力

9 9 4
....#....
....#....
....#....
.........
###...###
.........
....#....
....#....
....#....

出力

5

サンプル 4

入力

8 12 7
.###...#...#
..#..###...#
#.#...###...
...#....#...
....#..##.##
..#.#####...
.##..##.#...
##..###.#...

出力

7