[NOIP2008 普及组] 立体图

算法：(字符串处理,模拟,坐标变换) 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

接下来还需要确定投影之后的二维平面的范围：

    横坐标最多有：3 * 50 + 2 * 50 + 1（50是最大范围；3是z 每变1，横坐标变3；2是x 每变1，横坐标变2）

    纵坐标最多有：4 * 50 + 2 * 50 + 1（50是最大范围；4是y 每变1，纵坐标变4；2是x 每变1，纵坐标变2）

    注意：上述x，y，z是立体图形的坐标，"横坐标"和"纵坐标"是指平面图形的坐标。

    那么我们存储平面的二维数组开500*500就足够了，这也就是上面图片中的n=500的原因（当然你改成其他符合要求的值也可以哈~）

最后将二维投影平面的范围内的部分输出即可。

时间复杂度

每个小立方体均需要画一次，每次需要画 6 * 7 = 42个字符，因此总时间复杂度是 O(42nmh)，其中 n,m,h分别表示长宽高。

C++ 代码

#include <cstdio>
#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;
}

上一篇笔误，修正，辛苦管理重新查看~