【题解】P3326 [SDOI2015] 立体图

FrankSteven · 2025-01-14 09:06:39 · 题解

P3326 [SDOI2015] 立体图

简要题意

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

思路分析和做法参考

光的混合符合二进制或的原则，所以可以对光进行编码，用一个三位二进制数来表示一种光。

分别计算每一个三角形区域的颜色，再绘制到画布上就可以完成。

现来分析光线对三角形区域颜色的影响，给定的光可以分为正交 45° 的光和竖直向下的光。后者处理起来容易，只需要将所有顶面都预设为其颜色即可，然后考虑前者。

此处读者可以暂停阅读并拿出纸笔思考每一种光对于每一个三角形区域在什么情况下三角形区域不会点亮，观察规律。

这里提出我的做法：

观察相对位置的正方体高度会阻挡光线照射相应区域的最低相对高度有如下三类：

I型：
	2	2
1	1
*

II型：
	2	3
1	2
*

III型：	*	1	2	3	4

读者容易看出规律，接下来就是表示和找定义。

我将字符画按如下字母标识：

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型（二点钟）：
		2	3
	1	2
*	1

II型（二点钟）：
		3	3
	2	2
*	1

有些侧面的部分还需要按照上述光线模板下移一格，故我在表格中用如“-1I2”表示下移一格，两点钟方向 I 型。

将射线如下编码：

1	2	3
4	5	6
7	8	9

上表：

a	b	c	d	e	f	g	h	i	j	k	l
1	0I11	0I11	0I11	0I11	/	/	/	/	/	/	/	/
2	0III12	0III12	0III12	0III12	/	/	/	/	/	/	/	/
3	0I1	0I2	0I2	0I1	0II2	-1I2	-1I2	0II2	/	/	/	/
4	0III9	0III9	0III9	0III9	/	/	/	/	/	/	/	/
5	/	/	/	/	/	/	/	/	/	/	/	/
6	0III3	0III3	0III3	0III3	-1III3	-1III3	-1III3	-1III3	/	/	/	/
7	0I8	0I7	0I7	0I8	/	/	/	/	0II7	0II7	-1I7	-1I7
8	0III6	0III6	0III6	0III6	/	/	/	/	-1III6	-1III6	-1III6	-1III6
9	0I4	0I4	0I5	0I5	0II4	0II4	-1I4	-1I4	0II5	-1I5	-1I5	0II5

然后由此表编码即可完成此题

代码示例

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

代码解读

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<> 类，可以方便地完成按位或运算。

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;
}

这是检查被照亮的代码，我在编写的时候将 III 型归入了 I 然后再判断的，不过不影响直观，读者可以自行进一步改进代码。

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;
}

上述表格和主要的绘制逻辑。

由于笔者能力有限，代码尽力做到简洁清晰简明了，如有不妥当处请留下评论，笔者非常乐意起到抛砖引玉的作用。不过感兴趣的读者如果不满足于现有示例代码的运行效率，可以尝试优化，减少重复类型的枚举判断可以大幅度优化时间常数。这里已经足够通过此题，且考虑到只是作为一个思路的提示，就不作修改了。