E - イルミネーション (Illumination) Editorial /

Time Limit: 10 sec / Memory Limit: 256 MB

配点: 100

問題

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


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

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

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


入力

入力ファイルの 1 行目には 2 つの整数 W, H (1 \leq W \leq 100,1 \leq H \leq 100) が空白を区切りとして書かれている.続く H 行には JOI 社の建物の配置が書かれている. i + 1 行目 (1 \leq i \leq H) には W 個の整数が空白を 区切りとして書かれており, j 個目 (1 \leq j \leq 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