#P2227. The Wedding Juicer

    ID: 1228 远端评测题 2000ms 64MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>搜索BFS数据结构队列USACO 2005 January Gold

The Wedding Juicer

本题没有可用的提交语言。

题目描述

农夫约翰的奶牛们接了一份兼职工作,设计有趣的 punch-bowl( punch 碗)造型。设计步骤如下: 准备一块尺寸为 Wcm×HcmW cm×H cm 的平板(3W3003H3003≤W≤300,3≤H≤300)。 在平板的每个 1 cm×1 cm 的小方格上放置一个 1 cm×1 cm 的方块,每个方块有一个整数高度1B1,000,000,000 1≤B≤1,000,000,000)。

这些方块被小心地粘合在一起,因此 punch 不会从它们之间漏出。实际上,它们粘合得非常好,以至于角落的方块根本不会影响漏液问题!

然而,奶牛们始终无法计算出他们的碗设计能装多少 punch。假设碗是独立放置的(即碗周围没有特殊的墙壁),请计算碗能装多少 juice(果汁)。当然,有些碗会在边缘漏掉所有果汁,因此只能装 0。

输入格式 第 1 行:两个空格分隔的整数 W 和 H。

第 2 行到第H+1 H+1 行:第i+1 i+1 行包含碗的第 i 行高度,即 W 个空格分隔的整数,每个整数表示碗中某个方格的高度 B。第一个整数是第 1 列的高度,第二个整数是第 2 列的高度,依此类推。

输出格式

第 1 行:一个整数,表示描述的碗能装多少立方厘米(cc)的果汁。

示例输入

4 5
5 8 7 7
5 2 1 5
7 1 7 1
8 9 6 9
9 8 9 9

示例输出

12

提示

输出解释:

将两个高度为 1 的方块填充到高度 5,每个方块填充 4 cc。

将高度为 2 的方块填充到高度 5,填充 3 cc。

将高度为 6 的方块填充到高度 7,填充 1 cc。

总填充量: 2×4+3+1=122×4+3+1=12