← 返回题目列表

AtCoder · joi2012yo_e

E. 照明

中文机器翻译题面 查看原题

配点: 100 点

問題

JOI公司的建筑物如图所示,由 1 辺 1 米的正六边形连接而成。随着圣诞节临近,JOI公司决定用灯饰装饰建筑物的墙面。但是,由于在外部看不到的部分安装灯饰是没有意义的,因此灯饰只装饰那些可以从外部经过建筑物中而不进入室内的墙面。

JOI 社の建物の配置の例

上图是从高空俯视的JOI公司建筑物布局示例。正六边形内的数字表示坐标。灰色正六边形表示有建筑物的位置,白色正六边形表示没有建筑物的位置。在这个示例中,用红色实线表示的部分是将要装饰灯饰的墙面,该墙面的总长度为 64 米。

给定一张显示 JOI 建筑物布局的地图,编写一个程序来计算要装饰的墙壁的总长度。但是,您应该能够在地图外部自由移动,但不能在相邻建筑物之间自由移动。


入力

输入文件 1 在线 2 整数 W, H (1 \leqq W \leqq 100,1 \leqq H \leqq 100)以空格作为分隔符。继续 H 行描述了 JOI 建筑物的位置。i + 1 行目 (1 \leqq i \leqq H) 是 写入 W 整数以空格分隔,j 個目 (1 \leqq j \leqq 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