QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

#3251. 数正方体

統計

题目背景

学~霸~题

数正方体

题目描述

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

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

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

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

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

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

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

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

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

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

输入格式

从标准输入读入数据。

第一行两个正整数 $r,c$,表示图的高度和宽度。(注意不是 $n$ 和 $m$)

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

输出格式

输出到标准输出。

一行一个整数,表示正方体的数量。

样例输入

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

样例输出

14

样例解释

此时 $A$ 矩阵为 $\begin{bmatrix}3 & 3 & 2\\3 & 2 & 1\end{bmatrix}$,因为 $3+3+3+2+2+1=14$,所以图中共有 $14$ 个正方体。

子任务

保证 $1\le n,m \le 50$,$1\le A_{ij}\le 100$。(注意这里是 $n$ 和 $m$ 不是 $r$ 和 $c$)

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

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

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

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.