算法
(字符串处理,模拟,坐标变换) $O(42nmh)$
首先将一个小正方体的投影画出来:
char box[6][8] = {
"..+---+",
"./ /|",
"+---+ |",
"| | +",
"| |/.",
"+---+.."
};
然后为了正确处理遮挡关系,按照从后到前、从左到右、从下到上的顺序画每个小正方体即可。
两个坐标系如下所示,我们将最靠左、前、下的小立方体,和二维坐标系中左下角的点$(499, 0)$对齐。
然后观察可以发现二者的映射关系:设小立方体在 $(x, y, z)$ ,即第 $x$ 行第 $y$ 列第 $z$ 层, 则对于投影后的坐标而言:
- 横坐标:$z$ 每变1,横坐标变3,$x$ 每变1,横坐标变2;
- 纵坐标:$x$ 每变1,总坐标变2,$y$ 每变1,纵坐标变4
因此投影之后的左下角坐标是:
- 横坐标是 $499 - 3z - 2(n - 1 - x)$
- 纵坐标是 $2(n - 1 - x) + 4y$
接下来还需要确定投影之后的二维平面的范围。
最后将二维投影平面的范围内的部分输出即可。
时间复杂度
每个小立方体均需要画一次,每次需要画 6 * 7 = 42个字符,因此总时间复杂度是 $O(42nmh)$,其中 $n, m, h$ 分别表示长宽高。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500;
int n, m;
char box[6][8] = {
"..+---+",
"./ /|",
"+---+ |",
"| | +",
"| |/.",
"+---+.."
};
char g[N][N];
int h[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d", &h[i][j]);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
g[i][j] = '.';
int up = N, right = 0;
for (int x = 0; x < n; x ++ )
for (int y = 0; y < m; y ++ )
for (int z = 0; z < h[x][y]; z++)
{
int X = 499 - 2 * (n - 1 - x) - 3 * z;
int Y = 2 * (n - 1 - x) + 4 * y;
up = min(up, X - 5);
right = max(right, Y + 6);
for (int a = 0; a < 6; a++)
for (int b = 0; b < 7; b++)
if (box[a][b] != '.')
g[X - 5 + a][Y + b] = box[a][b];
}
for (int i = up; i < N; i++)
{
for (int j = 0; j <= right; j++) printf("%c", g[i][j]);
puts("");
}
return 0;
}
看完就懂了
orz
我以为y总表示的是m为长,n为宽,让我思考了半天
还是y总讲的清楚
为什么选499这个点而不是其他点?
499是数组最后的下标,这样用不需要计算画布多大