python/TangDou/CSP-J/AcWingTraining/T3/436.md

AcWing 436. 立体图

一、题目描述

小渊是个聪明的孩子，他经常会给周围的小朋友们讲解自己认为有趣的内容。最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。

小渊有一块面积为 m×n 的矩形区域，上面有 m×n 个边长为 1 的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是 $1$），小渊想请你 打印出这些格子的立体图。

我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放：

每个顶点用 1 个加号 + 表示，长用 3 个 − 表示，宽用 1 个 / 表示，高用两个 | 表示。

字符 +,−,/,| 的 ASCII 码分别为 $43，45，47，124$。

字符 . (ASCII 码 46)需要作为背景输出，即立体图里的空白部分需要用 . 来代替。

立体图的画法如下面的规则：

若两块积木左右相邻，图示为：

若两块积木上下相邻，图示为：

若两块积木前后相邻，图示为：

立体图中，定义位于第 (m,1) 的格子（即第 m 行第 1 列的格子）上面自底向上的第一块积木（即最下面的一块积木）的左下角顶点为整张图最左下角的点。(明显在提示你~)

输入格式 输入文件第一行有用空格隔开的两个整数 m 和 $n$，表示有 m×n 个格子。 

接下来的 m 行，是一个 m×n 的矩阵，每行有 n 个用空格隔开的整数，其中第 i 行第 j 列上的整数表示第 i 行第 j 列的格子上摞有多少个积木（$1$≤每个格子上的积木数$≤100$）。

输出格式 输出文件中包含题目要求的立体图，是一个 K 行 L 列的字符矩阵，其中 K 和 L 表示 最少需要 K 行 L 列才能按规定输出立体图。

数据范围 1≤m,n≤50

输入样例：

3 4
2 2 1 2
2 2 1 1
3 2 1 2

输出样例：

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

二、解题思路

全网最棒的讲解，而且是改变我$CSP-J$编程思路的一位老师

原来我听很多讲题，都是跟着老师的思路来，老师就是上帝视角，哪里有公式，哪里有陷阱，他是不会让你去跳坑的，一路推导后告诉你，这就是正解，你也是佩服无比，只好按老师的思路一点点理解消化。

结果，学习了一年，发现自己水平上涨不大，遇到题目依然是不会做，只能是看题解继续理解~，只能理解为自己智力不够，要不就是题目见的不够，再不就是努力不够，反正不是老师的原因。

今天在学习了$yxc$大佬的这道立体图后，再次被击倒！这$TM$也太难了，他是怎么想出来的！看不懂，理解不了！

然后就到$bilibili$上找，看看有没有人讲解过这道题，偶然发现了刘老师的讲解，才懂得原来世界上就没有神人，神人只不过是他的思考问题方式与我们不同而已，或者说，是他们掌握了正确的学习路径，我们的路径是错误的。

刘老师的办法就是 ① 仔细读题，抽象题意。 ② 解读用例，深入理解。 ③ 按正常人的思维去思考，让你去干你是怎么干的。

比如本题，就是先不管最后结果如何，我先把：

• 一个小方格怎么画

#include <bits/stdc++.h>

using namespace std;
// 画出一个格子
const int N = 2000; // 竞赛的内存空间一般不做严格限制,所以，能开大一点就开大一点
char a[N][N];       // 结果数组,一个立方体是7列，上下是6行,约7*50
char b[10][10] = {
    "  +---+", // b[0][2],5个字符
    " /   /|", // b[1][1],6个字符
    "+---+ |", // b[2][0],7个字符
    "|   | +", // b[3][0],7个字符
    "|   |/ ", // b[4][0],6个字符
    "+---+  "  // b[5][0],5个字符
};

// 试错思路
void draw(int i, int j) {
    memcpy(&a[i - 0][j], &b[5][0], 5); // 以(i,j)为左下角坐标进行,对于b[][]是从左下角开始粘贴
    memcpy(&a[i - 1][j], &b[4][0], 6);
    memcpy(&a[i - 2][j], &b[3][0], 7);
    memcpy(&a[i - 3][j], &b[2][0], 7);
    memcpy(&a[i - 4][j + 1], &b[1][1], 6);
    memcpy(&a[i - 5][j + 2], &b[0][2], 5);
}

int main() {
    int x = 1000, y = 1000; // 三维坐标系原点坐标
    draw(x, y);

    // 打印出来看看
    for (int i = x - 5; i <= x; i++) {
        for (int j = y; j <= y + 6; j++) {
            if (a[i][j] == 0)
                cout << '.';
            else
                cout << a[i][j];
        }
        cout << endl;
    }

    return 0;
}

• 从后到前，两个小方格怎么画

#include <bits/stdc++.h>

using namespace std;
const int N = 2000; // 竞赛的内存空间一般不做严格限制,所以，能开大一点就开大一点
char a[N][N];       // 结果数组,一个立方体是7列，上下是6行,约7*50
char b[10][10] = {
    "  +---+", // b[0][2],5个字符
    " /   /|", // b[1][1],6个字符
    "+---+ |", // b[2][0],7个字符
    "|   | +", // b[3][0],7个字符
    "|   |/ ", // b[4][0],6个字符
    "+---+  "  // b[5][0],5个字符
};

// 画出左右两个格子
void draw(int i, int j) {
    memcpy(&a[i - 0][j], &b[5][0], 5); // 以(i,j)为左下角坐标进行,对于b[][]是从左下角开始粘贴
    memcpy(&a[i - 1][j], &b[4][0], 6);
    memcpy(&a[i - 2][j], &b[3][0], 7);
    memcpy(&a[i - 3][j], &b[2][0], 7);
    memcpy(&a[i - 4][j + 1], &b[1][1], 6);
    memcpy(&a[i - 5][j + 2], &b[0][2], 5);
}
void print(int x, int y) {
    for (int i = x - 20; i <= x + 20; i++) {
        for (int j = y - 20; j <= y + 20; j++) {
            if (a[i][j] == 0)
                cout << '.';
            else
                cout << a[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    int x = 1000, y = 1000; // 三维坐标系原点坐标

    // 一个
    draw(x, y);
    print(x, y);

    // 两个,前后
    draw(x + 2, y - 2);
    print(x, y);

    // 三个,前后，x,两个两个加,y是两个两个减
    draw(x + 2 + 2, y - 2 - 2);
    print(x, y);

    return 0;
}

• 从左到右，两个小方格怎么画

#include <bits/stdc++.h>

using namespace std;
const int N = 2000; // 竞赛的内存空间一般不做严格限制,所以，能开大一点就开大一点
char a[N][N];       // 结果数组,一个立方体是7列，上下是6行,约7*50
char b[10][10] = {
    "  +---+", // b[0][2],5个字符
    " /   /|", // b[1][1],6个字符
    "+---+ |", // b[2][0],7个字符
    "|   | +", // b[3][0],7个字符
    "|   |/ ", // b[4][0],6个字符
    "+---+  "  // b[5][0],5个字符
};

// 画出左右两个格子
void draw(int i, int j) {
    memcpy(&a[i - 0][j], &b[5][0], 5); // 以(i,j)为左下角坐标进行,对于b[][]是从左下角开始粘贴
    memcpy(&a[i - 1][j], &b[4][0], 6);
    memcpy(&a[i - 2][j], &b[3][0], 7);
    memcpy(&a[i - 3][j], &b[2][0], 7);
    memcpy(&a[i - 4][j + 1], &b[1][1], 6);
    memcpy(&a[i - 5][j + 2], &b[0][2], 5);
}

void print(int x, int y) {
    for (int i = x - 20; i <= x + 20; i++) {
        for (int j = y - 20; j <= y + 20; j++) {
            if (a[i][j] == 0)
                cout << '.';
            else
                cout << a[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    int x = 1000, y = 1000; // 三维坐标系原点坐标

    // 画一个
    draw(x, y);
    print(x, y);
    // 画二个,第二个的列位置是y+4
    draw(x, y + 4);
    print(x, y);

    // 画三个,第三个的列位置是y+4
    draw(x, y + 4 + 4);
    print(x, y);
    return 0;
}

• 从下到上，两个小方格怎么画

#include <bits/stdc++.h>

using namespace std;
const int N = 2000; // 竞赛的内存空间一般不做严格限制,所以，能开大一点就开大一点
char a[N][N];       // 结果数组,一个立方体是7列，上下是6行,约7*50
char b[10][10] = {
    "  +---+", // b[0][2],5个字符
    " /   /|", // b[1][1],6个字符
    "+---+ |", // b[2][0],7个字符
    "|   | +", // b[3][0],7个字符
    "|   |/ ", // b[4][0],6个字符
    "+---+  "  // b[5][0],5个字符
};

// 画出左右两个格子
void draw(int i, int j) {
    memcpy(&a[i - 0][j], &b[5][0], 5); // 以(i,j)为左下角坐标进行,对于b[][]是从左下角开始粘贴
    memcpy(&a[i - 1][j], &b[4][0], 6);
    memcpy(&a[i - 2][j], &b[3][0], 7);
    memcpy(&a[i - 3][j], &b[2][0], 7);
    memcpy(&a[i - 4][j + 1], &b[1][1], 6);
    memcpy(&a[i - 5][j + 2], &b[0][2], 5);
}
void print(int x, int y) {
    for (int i = x - 20; i <= x + 20; i++) {
        for (int j = y - 20; j <= y + 20; j++) {
            if (a[i][j] == 0)
                cout << '.';
            else
                cout << a[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    int x = 1000, y = 1000; // 三维坐标系原点坐标

    // 画一个
    draw(x, y);
    print(x, y);

    draw(x - 3, y);
    print(x, y);

    draw(x - 3 - 3, y);
    print(x, y);
    return 0;
}

然后，这三个方向怎么个顺序呢？我的想法是$X,Y,Z$：

• $X$由小到大，就是从后向前，前面的盖住后面的，符合要求
• $Y$由小到大，就是从左向右，右面的盖住前面的，符合要求
• $Z$由小到大，就是从低到高，高的盖住低的，符合要求

   for (int i = 0; i < m; i++) {     // ① X由小到大，从后到前
        for (int j = 0; j < n; j++) { // ② Y由小到大，从左到右
            for (int k = 0; k < height; k++) // ③ 从下
            ...
        }
    }

我们提前准备一块大点的画布，信奥赛的比赛，一般对空间不是特别卡，所以，尽量开大一点，比如a[N][N],N=2010

然后我们把中心点$(1000,1000)$做为画笔的落笔点，那么它可能是向上下左右四个方向都可能画出来东西，我们也不知道具体的范围啊！ 没事，就先画出来再说，然后再想怎么把周围没用的去掉就行了。

继续思考上面的三层循环，我们发现，如果x=1000,y=1000,其实我们是

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

也就是第一个小方格在第一行(x=1000,y=1000)去画，第二行时，需要(x+2,y-2),这样就从第二行的开头进行绘制了！也就是换行时需要重新分配一下$x,y$的值！

    for (int i = 0; i < m; i++) {     // ① X由小到大，从后到前
        x += 2, y -= 2;               // 不断的调整起始位置
        for (int j = 0; j < n; j++) { // ② Y由小到大，从左到右
            for (int k = 0; k < height; k++) // ③ 从下往上
                ....
        }
    }

当执行到$...$时，就是要在$(x,y)$这个位置上，画一个高度为$k$的方格

根据上面三个方向的推导过程，我们知道:

• 高度每大$1$，$x$就减3,即x-3*k

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

• 向右移动$1$，$y$就加4,即y+4*j

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

  for (int i = 0; i < m; i++) {     // ① X由小到大，从后到前
        x += 2, y -= 2;               // 不断的调整起始位置
        for (int j = 0; j < n; j++) { // ② Y由小到大，从左到右
            cin >> height;
            for (int k = 0; k < height; k++) // ③ 从下往上
                draw(x - 3 * k, y + 4 * j);
        }
    }

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 2000; // 竞赛的内存空间一般不做严格限制,所以，能开大一点就开大一点
int m, n;           // m行n列
char a[N][N];       // 结果数组,一个立方体是7列，上下是6行,约7*50
char b[10][10] = {
    "  +---+", // b[0][2],5个字符
    " /   /|", // b[1][1],6个字符
    "+---+ |", // b[2][0],7个字符
    "|   | +", // b[3][0],7个字符
    "|   |/ ", // b[4][0],6个字符
    "+---+  "  // b[5][0],5个字符
};
int height, minx = 1000, maxy = 1000;

// 试错的思路
void draw(int i, int j) {
    memcpy(&a[i - 0][j], &b[5][0], 5);
    memcpy(&a[i - 1][j], &b[4][0], 6);
    memcpy(&a[i - 2][j], &b[3][0], 7);
    memcpy(&a[i - 3][j], &b[2][0], 7);
    memcpy(&a[i - 4][j + 1], &b[1][1], 6);
    memcpy(&a[i - 5][j + 2], &b[0][2], 5);
    minx = min(minx, i - 5);
    maxy = max(maxy, j + 6);
}

int main() {
    cin >> m >> n;
    int x = 1000, y = 1000; // 三维坐标系原点坐标
    // ① 绘制顺序：x,y,z:从后到前，从左到右，从下到上

    for (int i = 0; i < m; i++) {     // ① X由小到大，从后到前
        x += 2, y -= 2;               // 不断的调整起始位置
        for (int j = 0; j < n; j++) { // ② Y由小到大，从左到右
            cin >> height;
            for (int k = 0; k < height; k++) // ③ 从下往上
                draw(x - 3 * k, y + 4 * j);
        }
    }

    // 输出
    for (int i = minx; i <= x; i++) {
        for (int j = y; j <= maxy; j++) {
            if (a[i][j] == 0)
                cout << '.';
            else
                cout << a[i][j];
        }
        cout << endl;
    }
    return 0;
}