003 - イルミネーション (Illumination)

問題

JOI 社の建物は図のような 1 辺 1 メートルの正六角形をつなぎ合わせた形である．クリスマスが近づいているので，JOI 社では建物の壁面をイルミネーションで飾り付けることにした．ただし，外から見えない部分にイルミネーションを施すのは無駄なので，イルミネーションは外から建物の中を通らずに行くことのできる壁面にのみ飾り付けることにした．

図: JOI 社の建物の配置の例

上の図は上空から見た JOI 社の建物の配置の例である．正六角形内の数字は座標を表す．灰色の正六角形は建物がある場所を表し，白色の正六角形は建物がない場所を表す．この例では，赤の実線で示される部分がイルミネーションで飾り付けを行う壁面となり，その壁面の長さの合計は 64 メートルとなる．

JOI 社の建物の配置を表す地図が与えられたとき，飾り付けを行う壁面の長さの合計を求めるプログラムを作成せよ．ただし，地図の外側は自由に行き来できるものとし，隣接した建物の間は通ることはできないものとする．

入力

入力ファイルの 1 行目には 2 つの整数 W, H (1 ≦ W ≦ 100，1 ≦ H ≦ 100) が空白を区切りとして書かれている．続く H 行には JOI 社の建物の配置が書かれている．i + 1 行目 (1 ≦ i ≦ H) には W 個の整数が空白を区切りとして書かれており，j 個目 (1 ≦ j ≦ W) の整数は座標 (j, i) の正六角形に建物がある時は 1 であり，ない時は 0 である．また，与えられる入力データには建物が必ず 1 つ以上ある．

地図は以下の規則によって記述されている．

• 地図の最も北の行の最も西の正六角形は座標 (1, 1) である．
• 座標 (x, y) の正六角形に隣接する東隣の正六角形は座標 (x + 1, y) である．
• y が奇数の時，座標 (x, y) の正六角形に隣接する南西の正六角形の座標は (x, y + 1) である．
• y が偶数の時，座標 (x, y) の正六角形に隣接する南東の正六角形の座標は (x, y + 1) である．

出力

イルミネーションで飾り付けを行う壁面の長さの合計を 1 行で出力せよ．

入出力例

入力例 1

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

出力例 1

64

入出力例 1 は問題文中の例に対応しており，イルミネーションで飾り付けを行う壁面の長さの合計は 64 メートルである．

入力例 2

8 5
0 1 1 1 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 1 1 1 1
0 1 0 1 1 0 1 0
0 1 1 0 1 1 0 0

出力例 2

56