概要(ストーリー)
Eruiです。
私たち、スクールアイドルのグループ「ムーサ(古希)」は、全国のスクールアイドルを集めて踊ろうと企画したの。
Ozyomiです。
そこで、ウチのチームのリーダーが街の一角を貸し切り、その範囲内の建物を風船で覆おうと画策したっちゃ。
お金はメンバーの一人であるお姫様(真)が払ってくれるんやけど、建物を覆うのに必要な風船の数が分からんっちゃ。
NiCoです！
なるべくお金の無駄遣いはしたくないのでぇ、ビルを丁度覆える風船の数が知りたいニコぉ！
問題
風船を設置したい領域がある。
その領域内にある建物は、全て図のような一辺一メートルの所謂(いわゆる)六角形をつなぎ合わせた形である。
この建物全ての壁面を風船で覆いたい。
ただし、外から見えない部分を風船で覆うのは無駄なので、風船は外から建物の中を通らずに行くことの出来る壁面にのみ貼り付けることにした。
上の図は上空から見た領域内の建物の配置である。
正六角形内の数字は座標を表す。灰色は建物がある場所を表し、白色は建物がない場所を表す。
この例では、赤の実線で示される部分が風船を貼り付ける壁面となる。
建物がある座標一つ一つには、その場所の建物の高さが与えられ、一面につき風船は「建物の高さ(m)×10」個必要となる。一つの座標の建物の高さは、必ず一定であるとする。
領域内の建物の配置と高さを表す地図が与えられたとき、必要となる風船の数を求めるプログラムを作成せよ。
ただし、地図の外側は自由に行き来できるものとし、隣接した建物の間は通ることはできないものとする。
入力形式
空白区切りで整数w,h(1≦w≦100,1≦h≦100)が与えられる。
続くH行には領域内の建物の配置がかかれている。
i+1行目(1≦i≦H)にはW個の整数が空白を区切りとしてかかれており、j個目(1≦j≦W)の整数は座標(j,i)の正六角形に建物があるときはその建物の高さa(0
出力形式
必要な風船の最小の数を一行で出力せよ。
さんぷる入力１
8 4 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0
さんぷる出力１
640
さんぷる入力２
8 5 0 2 2 2 0 2 2 2 0 2 0 0 2 2 0 0 2 0 0 2 2 2 2 2 0 2 0 2 2 0 2 0 0 2 2 0 2 2 0 0
さんぷる出力２
1120
余談
今期生徒会長になりました・・・ぐるぐるぐるすぱーん！ hnkでう！