题解：P1058 [NOIP2008 普及组] 立体图

· · 题解

题解：P1058 [NOIP2008 普及组] 立体图

这道题目其实就是朴素的算算下表就能通过。

1. 解题思路

我们可以采用画布思想，先把整个数组都变成 .，在这里可以使用 fill 来实现，大致就是这样：fill(&a[0][0], &a[maxn - 1][maxn - 1], '.')。

我们定义一个 draw 函数，传的参数就是你要在 i 行 j 列画出一个立方体。详见下面：

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

其中标记 * 的点就是 i 行 j 列的点，也就是 draw 函数的参数。draw 就是传入 i 和 j，画出一个 * 在 i 行 j 列的立方体。

随后，我们考虑应该按照什么顺序来画立方体。注意到立方体们会互相覆盖，所以我们一层一层的盖楼，每一层从左上角开始，一行一行搭建，这样搭满一层。

形式化的讲，先从一层一层的搭建，每一层从下标为 (1,1) 开始搭建，搭到 (n,m)。搭建顺序是：

(1,1) \to (1,2) \to (1,3) \to \dots \to (1,m) \to \\ \vdots \\ \to (n,1) \to (n,2) \to (n,3) \to \dots \to (n, m)

顺序讲完了，该说说下标问题了。考虑三种情况，分别是在二维数组下标 i 行 j 列的立方体向右、前、上搭建第 k 一个立方体的下标。

  1. 向右搭建（right）：下标是 (i, j+4k)。
  2. 向前搭建（front）：下标是 (i+2k, j-2k)。
  3. 向上搭建（up）：下标是 (i-3k, j)。

这些下表都要自己算一遍。

但是，计算这个图形要多大的数组很难，所以可以直接从中间开始画，画完之后再去确定最大最小的横纵坐标即可。

2. 代码实现

思路明白了，代码很好写。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 60;
const int maxm = 3010;
const int st = maxm >> 1;
int n, m, a[maxn][maxn], mxheight;
int stx = maxm, sty = maxm, edx, edy;
char ans[maxm][maxm]; 
void draw(int x, int y) {
    ans[x][y + 2] = ans[x][y + 6] = ans[x + 2][y] = 
    ans[x + 2][y + 4] = ans[x + 3][y + 6] = ans[x + 5][y] = 
    ans[x + 5][y + 4] = '+';
    ans[x + 1][y + 1] = ans[x + 1][y + 5] = ans[x + 4][y + 5] = '/';
    ans[x][y + 3] = ans[x][y + 4] = ans[x][y + 5] = 
    ans[x + 2][y + 1] = ans[x + 2][y + 2] = ans[x + 2][y + 3] =
    ans[x + 5][y + 1] = ans[x + 5][y + 2] = ans[x + 5][y + 3] = '-';
    ans[x + 1][y + 6] = ans[x + 2][y + 6] = ans[x + 3][y] =
    ans[x + 4][y] = ans[x + 3][y + 4] = ans[x + 4][y + 4] = '|';
    ans[x + 1][y + 2] = ans[x + 1][y + 3] = ans[x + 1][y + 4] = ' ';
    ans[x + 2][y + 5] = ans[x + 3][y + 5] = ' ';
    ans[x + 3][y + 1] = ans[x + 3][y + 2] = ans[x + 3][y + 3] = ' ';
    ans[x + 4][y + 1] = ans[x + 4][y + 2] = ans[x + 4][y + 3] = ' ';
}
void print() {
    for (int i = stx; i <= edx; i++) {
        for (int j = sty; j <= edy; j++) cout << ans[i][j];
        cout << "\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    fill(&ans[0][0], &ans[maxm - 1][maxm - 1], '.');
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) cin >> a[i][j], mxheight = max(mxheight, a[i][j]);
    // right: draw(i, j + 4k);
    // front: draw(i + 2k, j + (-2k));
    // up:    draw(i + (-3k), j);
    for (int h = 1; h <= mxheight; h++) {
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= m; j++) 
                if (a[i][j] >= h) draw(st + (i - 1) * 2 - 3 * (h - 1), st + (j - 1) * 4 - 2 * (i - 1));
    }
    for (int i = 1; i < maxm - 30; i++) 
        for (int j = 1; j < maxm - 30; j++) 
            if (ans[i][j] != '.') {
                stx = min(stx, i);
                sty = min(sty, j);
                edx = max(edx, i);
                edy = max(edy, j);
            }
    print();
    return 0;
}