#L6817. 「THUPC 2022 初赛」数正方体

    ID: 4657 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>模板匹配深度优先搜索记忆化搜索动态规划增量计算

「THUPC 2022 初赛」数正方体

题目背景
学霸题
数正方体


题目描述
小 E 有一块面积为 n×mn \times m 的矩形区域,上面有 n×mn \times m 个边长为 11 的格子,第 iijj 列的格子上堆了 AijA_{ij} 个同样大小的正方体积木。小 E 做了某道题之后,突发奇想把这些正方体画成了字符画,然后让你帮他数一数他一共有多少个正方体。我们定义每个正方体为如下格式,并且不会做任何旋转,只会严格以这一种形式摆放:

..+---+
./   /|  高
+---+ |
|   | +
|   |/.  宽
+---+..
   长

每个顶点用 11+ 表示,长用 33- 表示,宽用 11/ 表示,高用两个 | 表示。字符 . 作为背景。中间的空白是空格(ASCII 码为 3232)。

若两个正方体左右相邻,图示为:

..+---+---+
./   /   /|
+---+---+ |
|   |   | +
|   |   |/.
+---+---+..

若两个正方体积木上下相邻,图示为:

..+---+
./   /|
+---+ |
|   | +
|   |/|
+---+ |
|   | +
|   |/.
+---+..

若两个正方体前后相邻,图示为:

....+---+
.../   /|
..+---+ |
./   /| +
+---+ |/.
|   | +..
|   |/...
+---+....

位于前面的正方体的面会遮挡住位于后面的正方体的面。为了让你看得清楚,没有整列正方体被挡在后面,小 E 保证了 1AijAi1,j1 \le A_{ij} \le A_{i-1,j}1AijAi,j11 \le A_{ij} \le A_{i,j-1}。并且图中没有整行或者整列的 .。所以,一个字符画对应唯一的矩阵 AA,一个矩阵 AA 也对应一个唯一的字符画。


输入格式
第一行两个正整数 r,cr,c,表示图的高度和宽度。(注意不是 nnmm

接下来是一个 rrcc 列的字符画,表示小 E 堆叠的正方体。


输出格式
一行一个整数,表示正方体的数量。


样例
输入

14 17
....+---+---+....
.../   /   /|....
..+---+---+ |....
./   /|   | +---+
+---+ |   |/   /|
|   | +---+---+ |
|   |/   /|   | +
+---+---+ |   |/|
|   |   | +---+ |
|   |   |/   /| +
+---+---+---+ |/.
|   |   |   | +..
|   |   |   |/...
+---+---+---+....

输出

14

此时 AA 矩阵为

[332321]\begin{bmatrix}3 & 3 & 2\\3 & 2 & 1\end{bmatrix}

因为 3+3+3+2+2+1=143+3+3+2+2+1=14,所以图中共有 1414 个正方体。


数据范围与提示
保证 1n,m501 \le n,m \le 501Aij1001 \le A_{ij} \le 100。(注意这里是 nnmm 不是 rrcc

保证 1<in,AijAi1,j\forall 1 < i \le n, A_{ij} \le A_{i-1,j}

保证 1<j<m,AijAi,j1\forall 1 < j < m, A_{ij} \le A_{i,j-1}

保证字符画中没有一整行或者一整列是 .