問題8: 全てのマスを連結するときの最小コスト (hard) Perl編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
この問題は前問 (問題8: 全てのマスを連結するときの最小コスト) の制約強化版です。
グリッド状の盤面が与えられます。盤面上で2つのマスを連結するコストは2つのマスの数値の積です。上下左右にマスを連結して、すべてのマスがマスを介して連結するための最小のコストを求めてください。
初期の盤面では各マスはいずれのマスとも連結していないものとします。
※この問題は、paiza開発日誌で詳しく解説しています
- 入力される値
-
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}
・ 1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・ 続く h 行のうち i 行目には、i 行目のマスの数値を表す整数値のリスト t_i が与えられます。
・ t_{i,j} は i 行目の j 列目のマスの数値です。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
最小のコストを 1 行で出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ h , w ≦ 300
・ 0 ≦ t_{i,j} ≦ 100 (0 ≦ i < h, 0 ≦ j < w)
- 入力例1
-
3 3
3 1 4
1 5 9
2 6 5
- 出力例1
-
95
