洛谷P8217 [THUPC2022 初赛] 数正方体题解

题目链接：P8217 [THUPC2022 初赛] 数正方体

题意：

小 E 有一块面积为 $n\times m$ 的矩形区域，上面有 $n\times m$ 个边长为 $1$ 的格子，第 $i$ 行 $j$ 列的格子上堆了 $ A_{i,j}$ 个同样大小的正方体积木。小 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堆叠的正方体。

输出格式：

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

数据范围：

保证 $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}$。

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

观察样例

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

题目保证前面的方块不会比后面的多，那么这题其实非常非常简单。

我们可以依次考虑每一列，然后在正面从下往上摸过去，可以往里摸就说明外面这一层到头了。

继续往里摸也是一样的，于是我们就解决了这个问题。（一开始还以为是大模拟）

时间复杂度 $\mathcal{O}(r\cdot c)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

int res, cnt; string s[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int r,c; cin >> r >> c;
    for(int i = 0; i <= r; i++) { getline(cin, s[i]), s[i] = "#" + s[i]; }
    // for(int i = 1; i <= r; i++) cout << s[i] << '\n';
    for(int i = 1; i <= c; i += 4)
    {
        int x = r, y = i; cnt = 0;
        while(x >= 1 && y <= c)
        {
            if(x - 1 >= 1 && y + 1 <= c && s[x - 1][y + 1] == '/') {
                x -= 2; y += 2; res += cnt;
            }else if(x - 1 >= 1 && s[x - 1][y] == '|') {
                x -= 3; ++cnt;
            }else { x -= 2; y += 2; }
        }
    }
    cout << res << '\n';
    return 0;
}