专栏文章

【题解】P3326 [SDOI2015] 立体图

FFrankSteven
P3326题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqiqvyi
此快照首次捕获于
2025/12/04 05:28
3 个月前
此快照最后确认于
2025/12/04 05:28
3 个月前
查看原文

P3326 [SDOI2015] 立体图

简要题意

给定一个网格内正方体堆叠图的俯瞰图，一个九宫格表示不同方向平行光的颜色，建立右手坐标系 {i,j,k}\left\{\bold i,\bold j,\bold k\right\}，中间为方向 (0,0,−1)\left(0,0,-1\right) 的光，四周方向为 (m,n,−1) m,n∈{0,−1} m≠n\left(m,n,-1\right)\ m,n\in \left\{0,-1\right\}\ m\ne n，四角方向为 (m,n,−1) m,n∈{1,−1}\left(m,n,-1\right)\ m,n\in \left\{1,-1\right\}。颜色初始给定“RGB”或者没有光“*”，混合符合光学，用“RGBCPYWK”表示。

思路分析和做法参考

光的混合符合二进制或的原则，所以可以对光进行编码，用一个三位二进制数来表示一种光。
分别计算每一个三角形区域的颜色，再绘制到画布上就可以完成。
现来分析光线对三角形区域颜色的影响，给定的光可以分为正交 45°45° 的光和竖直向下的光。后者处理起来容易，只需要将所有顶面都预设为其颜色即可，然后考虑前者。
此处读者可以暂停阅读并拿出纸笔思考每一种光对于每一个三角形区域在什么情况下三角形区域不会点亮，观察规律。
这里提出我的做法：
观察相对位置的正方体高度会阻挡光线照射相应区域的最低相对高度有如下三类：
I型：
33
22
11
*
II型：
34
23
12
*
III型：
*1234
读者容易看出规律，接下来就是表示和找定义。
我将字符画按如下字母标识：
CPP
const string Cube[] = {
	R"(    +-------+)",
	R"(   /d\aaaa'/|)",
	R"(  /dd.*'bb/e|)",
	R"( /.cccc\b/e/|)",
	R"(+-------+e.f|)",
	R"(|\iiiii/|\:f|)",
	R"(|l\iii/j|h*f|)",
	R"(|ll\i/jj|h:\|)",
	R"(|lllXjjj|h'g+)",
	R"(|ll/k\jj|/g/ )",
	R"(|l/kkk\j|g/  )",
	R"(|/kkkkk\|/   )",
	R"(+-------+    )"
};
按照时钟方向标志斜向光方向
如上图分类中 I 和 II 型为一点钟方向，而如下图则为两点钟方向，III 型示例为三点钟方向：
I型（二点钟）：
3
23
12
*1
II型 （二点钟）：
4
33
22
*1
有些侧面的部分还需要按照上述光线模板下移一格，故我在表格中用如“-1I2”表示下移一格，两点钟方向 I 型。
将射线如下编码：
123
456
789
上表：
abcdefghijkl
10I110I110I110I11////////
20III120III120III120III12////////
30I10I20I20I10II2-1I2-1I20II2////
40III90III90III90III9////////
5////////////
60III30III30III30III3-1III3-1III3-1III3-1III3////
70I80I70I70I8////0II70II7-1I7-1I7
80III60III60III60III6////-1III6-1III6-1III6-1III6
90I40I40I50I50II40II4-1I4-1I40II5-1I5-1I50II5
然后由此表编码即可完成此题

代码示例

CPP
#include <bits/stdc++.h>
using namespace std;

const string ColorSign = "KBGCRPYW";
struct color : bitset<3> {
	color() { bitset(0); }
	char sign() { return ColorSign[to_ulong()]; }
};

bitset<3> getCol(char c) {
	switch (c) {
		case 'R': return bitset<3>(0b100);
		case 'G': return bitset<3>(0b010);
		case 'B': return bitset<3>(0b001);
	}
	return bitset<3>(0b000);
}

struct canvas : vector<string> {
	int x, y, z;
	canvas(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {
		resize(z*8+x*4+1, string(y*8+x*4+1, ' '));
	}
};

const string Cube[] = {
	R"(    +-------+)",
	R"(   /d\aaaa'/|)",
	R"(  /dd.*'bb/e|)",
	R"( /.cccc\b/e/|)",
	R"(+-------+e.f|)",
	R"(|\iiiii/|\:f|)",
	R"(|l\iii/j|h*f|)",
	R"(|ll\i/jj|h:\|)",
	R"(|lllXjjj|h'g+)",
	R"(|ll/k\jj|/g/ )",
	R"(|l/kkk\j|g/  )",
	R"(|/kkkkk\|/   )",
	R"(+-------+    )"
};

struct block {
	int x, y, z;
	vector<color> col;
	block(int _x, int _y, int _z) : x(_x), y(_y), z(_z), col(12, color()) {}
	void print(canvas &mat) {
		for(int i = 0; i < 13; ++i)
			for(int j = 0; j < 13; ++j) {
				if(Cube[i][j] == ' ') continue;
				if(Cube[i][j] == 'X' || !isalpha(Cube[i][j]))
					mat[mat.z*8-z*8+x*4-8+i][mat.x*4+y*8-x*4-4+j] = Cube[i][j];
				else mat[mat.z*8-z*8+x*4-8+i][mat.x*4+y*8-x*4-4+j] = col[Cube[i][j]-'a'].sign();
			}
	}
};

template <typename T>
using mat = vector<vector<T>>;

struct Laser {
	int ty, dir;
};

const int Direction[12][2] = {
	{-1, 1}, {-1, 1}, { 0, 1},
	{ 1, 1}, { 1, 1}, { 1, 0},
	{ 1,-1}, { 1,-1}, { 0,-1},
	{-1,-1}, {-1,-1}, {-1, 0}
};

bool CheckSight(const mat<int> &a,
				size_t x, size_t y, int z, Laser l) {
	if(l.ty == 0) return 0;
	int m = (l.ty == 2) * -1;
	int k = 1 - (l.dir & 1);
	auto [i, j] = Direction[l.dir - 1];
	int x_ = x + k * -1 * i, y_ = y + (k - 1) * j, z_ = z + m;
	for(x += i, y += j, z++;
		x >= 0 && x < a.size() &&
		y >= 0 && y < a[0].size();
		x += i, y += j, z++) {
		if(a[x][y] >= z) return 0;
	}
	if(l.dir % 3 == 0) return 1;
	x = x_, y = y_, z = z_;
	for(x += i, y += j, z++;
		x >= 0 && x < a.size() &&
		y >= 0 && y < a[0].size();
		x += i, y += j, z++) {
		if(a[x][y] >= z) return 0;
	}
	return 1;
}

const int LaserTypes[9][12][3] = {
	{
		{ 0, 1,11}, { 0, 1,11}, { 0, 1,10}, { 0, 1,10},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1,12}, { 0, 1,12}, { 0, 1,12}, { 0, 1,12},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 1}, { 0, 1, 2}, { 0, 1, 2}, { 0, 1, 1},
		{ 0, 2, 2}, {-1, 1, 2}, {-1, 1, 2}, { 0, 2, 2},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 9}, { 0, 1, 9}, { 0, 1, 9}, { 0, 1, 9},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 3}, { 0, 1, 3}, { 0, 1, 3}, { 0, 1, 3},
		{-1, 1, 3}, {-1, 1, 3}, {-1, 1, 3}, {-1, 1, 3},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 8}, { 0, 1, 7}, { 0, 1, 7}, { 0, 1, 8},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 2, 7}, { 0, 2, 7}, {-1, 1, 7}, {-1, 1, 7},
	},
	{
		{ 0, 1, 6}, { 0, 1, 6}, { 0, 1, 6}, { 0, 1, 6},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{-1, 1, 6}, {-1, 1, 6}, {-1, 1, 6}, {-1, 1, 6},
	},
	{
		{ 0, 1, 4}, { 0, 1, 4}, { 0, 1, 5}, { 0, 1, 5},
		{ 0, 2, 4}, { 0, 2, 4}, {-1, 1, 4}, {-1, 1, 4},
		{ 0, 2, 5}, {-1, 1, 5}, {-1, 1, 5}, { 0, 2, 5},
	}
};
int main() {
	int X, Y, Z = 0;
	cin >> X >> Y;
	mat<int> arr(X,vector<int>(Y));
	vector<char> L(9);
	for(auto &r : arr)
		for(auto &_ : r) {
			cin >> _;
			Z = max(_,Z);
			_--;
		}
	for(auto &_ : L) cin >> _;
	canvas c(X, Y, Z);
	for(int z = 0; z < Z; ++z) 
		for(int x = 0; x < X; ++x) 
			for(int y = 0; y < Y; ++y) 
				if(arr[x][y] - z >= 0) {
					block tmp{x, y, z};
					for(int d = 0; d < 4; ++d)
						tmp.col[d] |= getCol(L[4]);
					for(int l = 0; l < 9; ++l)
						for(int d = 0; d < 12; ++d)
							if(CheckSight(arr, x, y,
								z + LaserTypes[l][d][0],
								{LaserTypes[l][d][1],
									LaserTypes[l][d][2]}))
								tmp.col[d] |= getCol(L[l]);
					tmp.print(c);
				}
	bool INITIAL = 0;
	for(auto s : c)
		if(!INITIAL) {
			if(*max_element(s.begin(),s.end()) == ' ') continue;
			INITIAL = 1;
			cout << s << "\n";
		} else cout << s << "\n";
	return 0;
}

代码解读

CPP
const string ColorSign = "KBGCRPYW";
struct color : bitset<3> {
	color() { bitset(0); }
	char sign() { return ColorSign[to_ulong()]; }
};

bitset<3> getCol(char c) {
	switch (c) {
		case 'R': return bitset<3>(0b100);
		case 'G': return bitset<3>(0b010);
		case 'B': return bitset<3>(0b001);
	}
	return bitset<3>(0b000);
}
这部分是关于颜色的逻辑，我继承了 std::bitset<> 类，可以方便地完成按位或运算。
CPP
struct canvas : vector<string> {
	int x, y, z;
	canvas(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {
		resize(z*8+x*4+1, string(y*8+x*4+1, ' '));
	}
};

const string Cube[] = {
	R"(    +-------+)",
	R"(   /d\aaaa'/|)",
	R"(  /dd.*'bb/e|)",
	R"( /.cccc\b/e/|)",
	R"(+-------+e.f|)",
	R"(|\iiiii/|\:f|)",
	R"(|l\iii/j|h*f|)",
	R"(|ll\i/jj|h:\|)",
	R"(|lllXjjj|h'g+)",
	R"(|ll/k\jj|/g/ )",
	R"(|l/kkk\j|g/  )",
	R"(|/kkkkk\|/   )",
	R"(+-------+    )"
};

struct block {
	int x, y, z;
	vector<color> col;
	block(int _x, int _y, int _z) : x(_x), y(_y), z(_z), col(12, color()) {}
	void print(canvas &mat) {
		for(int i = 0; i < 13; ++i)
			for(int j = 0; j < 13; ++j) {
				if(Cube[i][j] == ' ') continue;
				if(Cube[i][j] == 'X' || !isalpha(Cube[i][j]))
					mat[mat.z*8-z*8+x*4-8+i][mat.x*4+y*8-x*4-4+j] = Cube[i][j];
				else mat[mat.z*8-z*8+x*4-8+i][mat.x*4+y*8-x*4-4+j] = col[Cube[i][j]-'a'].sign();
			}
	}
};
这是画布和小立方体的绘制部分，定义了颜色数组完成各个面的绘制，并处理坐标转换，便于后续编写。
CPP
template <typename T>
using mat = vector<vector<T>>;

struct Laser {
	int ty, dir;
};
这是一些简单的定义，便于后续传参。
CPP
const int Direction[12][2] = {
	{-1, 1}, {-1, 1}, { 0, 1},
	{ 1, 1}, { 1, 1}, { 1, 0},
	{ 1,-1}, { 1,-1}, { 0,-1},
	{-1,-1}, {-1,-1}, {-1, 0}
};

bool CheckSight(const mat<int> &a,
				size_t x, size_t y, int z, Laser l) {
	if(l.ty == 0) return 0;
	int m = (l.ty == 2) * -1;
	int k = 1 - (l.dir & 1);
	auto [i, j] = Direction[l.dir - 1];
	int x_ = x + k * -1 * i, y_ = y + (k - 1) * j, z_ = z + m;
	for(x += i, y += j, z++;
		x >= 0 && x < a.size() &&
		y >= 0 && y < a[0].size();
		x += i, y += j, z++) {
		if(a[x][y] >= z) return 0;
	}
	if(l.dir % 3 == 0) return 1;
	x = x_, y = y_, z = z_;
	for(x += i, y += j, z++;
		x >= 0 && x < a.size() &&
		y >= 0 && y < a[0].size();
		x += i, y += j, z++) {
		if(a[x][y] >= z) return 0;
	}
	return 1;
}
这是检查被照亮的代码，我在编写的时候将 III 型归入了 I 然后再判断的，不过不影响直观，读者可以自行进一步改进代码。
CPP
const int LaserTypes[9][12][3] = {
	{
		{ 0, 1,11}, { 0, 1,11}, { 0, 1,10}, { 0, 1,10},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1,12}, { 0, 1,12}, { 0, 1,12}, { 0, 1,12},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 1}, { 0, 1, 2}, { 0, 1, 2}, { 0, 1, 1},
		{ 0, 2, 2}, {-1, 1, 2}, {-1, 1, 2}, { 0, 2, 2},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 9}, { 0, 1, 9}, { 0, 1, 9}, { 0, 1, 9},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 3}, { 0, 1, 3}, { 0, 1, 3}, { 0, 1, 3},
		{-1, 1, 3}, {-1, 1, 3}, {-1, 1, 3}, {-1, 1, 3},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
	},
	{
		{ 0, 1, 8}, { 0, 1, 7}, { 0, 1, 7}, { 0, 1, 8},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{ 0, 2, 7}, { 0, 2, 7}, {-1, 1, 7}, {-1, 1, 7},
	},
	{
		{ 0, 1, 6}, { 0, 1, 6}, { 0, 1, 6}, { 0, 1, 6},
		{ 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0}, { 0, 0, 0},
		{-1, 1, 6}, {-1, 1, 6}, {-1, 1, 6}, {-1, 1, 6},
	},
	{
		{ 0, 1, 4}, { 0, 1, 4}, { 0, 1, 5}, { 0, 1, 5},
		{ 0, 2, 4}, { 0, 2, 4}, {-1, 1, 4}, {-1, 1, 4},
		{ 0, 2, 5}, {-1, 1, 5}, {-1, 1, 5}, { 0, 2, 5},
	}
};
int main() {
	int X, Y, Z = 0;
	cin >> X >> Y;
	mat<int> arr(X,vector<int>(Y));
	vector<char> L(9);
	for(auto &r : arr)
		for(auto &_ : r) {
			cin >> _;
			Z = max(_,Z);
			_--;
		}
	for(auto &_ : L) cin >> _;
	canvas c(X, Y, Z);
	for(int z = 0; z < Z; ++z) 
		for(int x = 0; x < X; ++x) 
			for(int y = 0; y < Y; ++y) 
				if(arr[x][y] - z >= 0) {
					block tmp{x, y, z};
					for(int d = 0; d < 4; ++d)
						tmp.col[d] |= getCol(L[4]);
					for(int l = 0; l < 9; ++l)
						for(int d = 0; d < 12; ++d)
							if(CheckSight(arr, x, y,
								z + LaserTypes[l][d][0],
								{LaserTypes[l][d][1],
									LaserTypes[l][d][2]}))
								tmp.col[d] |= getCol(L[l]);
					tmp.print(c);
				}
	bool INITIAL = 0;
	for(auto s : c)
		if(!INITIAL) {
			if(*max_element(s.begin(),s.end()) == ' ') continue;
			INITIAL = 1;
			cout << s << "\n";
		} else cout << s << "\n";
	return 0;
}
上述表格和主要的绘制逻辑。
由于笔者能力有限，代码尽力做到简洁清晰简明了，如有不妥当处请留下评论，笔者非常乐意起到抛砖引玉的作用。不过感兴趣的读者如果不满足于现有示例代码的运行效率，可以尝试优化，减少重复类型的枚举判断可以大幅度优化时间常数。这里已经足够通过此题，且考虑到只是作为一个思路的提示，就不作修改了。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...