输出一个立体图在不同方向的彩色光照下看上去的样子。
题目大意
给出一个 n×mn\times mn×m 的矩形区域，区域包含 n×mn\times mn×m 个边长为 111 的格子，每个格子上有一定数量的单位立方体。九个方向中，从每个方向上可能有一束颜色为红绿蓝之一的平行光。输出这些立方体看上去的样子。
具体题意请到OJ阅读。
题目链接
题解
之前从网上完全找不到题解啊！对拍都没法拍！
题目的数据范围很小，因此只需模拟即可。对于一个方向的平行光，可以将每个立方体投影到一个垂直于光线方向的平面上，然后处理立方体在平面上的覆盖情况，进而计算出立方体表面的每个部分上每种颜色的光照情况。而立方体在平面上的投影可以方便的用坐标变换来表示。
以从右前方入射的光线为例，如果我们从后向前，从左向右，从下向上建立三维直角坐标系的话，则变换
(x,y,z)→(x−z,y−z)(x,y,z)\to(x-z,y-z)(x,y,z)→(x−z,y−z)可以视为将立方体投影到与该方向光线垂直的一个平面的一个变换。而位于 (u,v)(u,v)(u,v) 的立方体的投影最多会被六个其它投影所遮挡：
(u−1,v)(u−1,v−1)(u,v−1)(u+1,v)(u+1,v+1)(u,v+1) \begin{array}{c} (u-1,v)\quad(u-1,v-1)\quad(u,v-1)\\ (u+1,v)\quad(u+1,v+1)\quad(u,v+1) \end{array} (u−1,v)(u−1,v−1)(u,v−1)(u+1,v)(u+1,v+1)(u,v+1)只需逐个判断并记录遮挡状况即可。
对每个立方体计算出光照情况后，只需将立方体从后向前，从左向右，从下向上的逐个输出到一个虚拟画布上，再将答案从画布输出即可。
代码
这个题的实现中我使用了巨量状态压缩和常量数组来存储立方体的覆盖情况和模拟覆盖过程，代码也缺少注释，因此可读性较差。建议以自己的方法实现程序，然后可以和我的代码对拍。然而我的代码长度也是提交的人里最短的
#include <cstdio>
#include <algorithm>
const int MAXN = 110;
int sgnd(int x, int s) {
return s < 0 ? 100 - x : s * x + 1;
}
int n = 0, m = 0;
int h[MAXN][MAXN];
int lay[MAXN * 2][MAXN * 2];
struct Cube {
short clr[3]; // 0:r, 1:g, 2:b
//*3*2*1*0U3U2U1U0F3F2F1F0R3R2R1R0
/*
+-------+
|\11111/|
|2\111/0|
|22\1/00|
|222X000|
|22/3\00|
|2/333\0|
|/33333\|
+-------+
*/
Cube() {
clr[0] = 0;
clr[1] = 0;
clr[2] = 0;
}
char color(int pos) {
return ("KBGCRPYW")[(((clr[0] >> pos) & 1) << 2) | (((clr[1] >> pos) & 1) << 1) | ((clr[2] >> pos) & 1)];
}
} c[MAXN][MAXN][MAXN];
int obs[9][7] = {{0xF00, 0x300, 0x000, 0xC00, 0xF00, 0xF00, 0xF00}, {0xF00, 0x000, 0xF00}, {0xF0F, 0x609, 0x00F, 0x90F, 0xF0F, 0xF06, 0xF00}, {0xF00, 0x000, 0xF00}, {0xF00}, {0xF0F, 0x00F, 0xF00}, {0xFF0, 0x9F0, 0x0F0, 0x6C0, 0xF00, 0xF30, 0xFF0}, {0xFF0, 0x0F0, 0xF00}, {0xFFF, 0xCFC, 0x0FF, 0x39F, 0xF0F, 0xF63, 0xFF0}};
int par1[9][8] = {{-1, 0, -1, 200, 0, -1, -1, 200}, {-1, 0, -1, 200, 0, 1, 0, 0}, {-1, 0, -1, 200, 0, 1, -1, 100}, {0, -1, -1, 200, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, -1, 100, 1, 0, 0, 0}, {1, 0, -1, 100, 0, -1, -1, 200}, {1, 0, -1, 100, 0, 1, 0, 0}, {1, 0, -1, 100, 0, 1, -1, 100}}, par2[9][4];
int of1[6][2] = {{-1, 0}, {-1, -1}, {0, -1}, {1, 0}, {1, 1}, {0, 1}}, of2[2] = {-1, 1};
char fra[15][15] = {
{'+', '-', '-', '-', '-', '-', '-', '-', '+', -1, -1, -1, -1},
{'|', '/', 7, 7, 7, 7, 7, '\\', '|', '/', -1, -1, -1},
{'|', 6, '/', 7, 7, 7, '\\', 4, '|', 3, '/', -1, -1},
{'|', 6, 6, '/', 7, '\\', 4, 4, '|', '/', 3, '/', -1},
{'|', 6, 6, 6, 'X', 4, 4, 4, '|', 2, '\'', 3, '+'},
{'|', 6, 6, '\\', 5, '/', 4, 4, '|', 2, ':', '\\', '|'},
{'|', 6, '\\', 5, 5, 5, '/', 4, '|', 2, '*', 0, '|'},
{'|', '\\', 5, 5, 5, 5, 5, '/', '|', '\\', ':', 0, '|'},
{'+', '-', '-', '-', '-', '-', '-', '-', '+', 1, '.', 0, '|'},
{-1, '/', '.', 11, 11, 11, 11, '\\', 8, '/', 1, '/', '|'},
{-1, -1, '/', 10, 10, '.', '*', '\'', 8, 8, '/', 1, '|'},
{-1, -1, -1, '/', 10, '\\', 9, 9, 9, 9, '\'', '/', '|'},
{-1, -1, -1, -1, '+', '-', '-', '-', '-', '-', '-', '-', '+'}};
char ans[14 * MAXN][14 * MAXN];
void solve(int x, int y, int l) {
if (x == 0 && y == 0) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
c[i][j][h[i][j] - 1].clr[l] |= 0xF00;
}
}
return;
}
for (int i = 0; i < MAXN * 2; i++) {
std::fill(lay[i], lay[i] + MAXN * 2, -1);
}
int *ob = obs[3 * (x + 1) + y + 1];
int *p1 = par1[3 * (x + 1) + y + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < h[i][j]; k++) {
int xind = p1[0] * i + p1[1] * j + p1[2] * k + p1[3] + 3, yind = p1[4] * i + p1[5] * j + p1[6] * k + p1[7] + 3, layer = sgnd(i, x) + sgnd(j, y) + sgnd(k, 1);
if (lay[xind][yind] < layer) {
lay[xind][yind] = layer;
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < h[i][j]; k++) {
int xind = p1[0] * i + p1[1] * j + p1[2] * k + p1[3] + 3, yind = p1[4] * i + p1[5] * j + p1[6] * k + p1[7] + 3, layer = sgnd(i, x) + sgnd(j, y) + sgnd(k, 1);
short cover = ob[0];
if (layer < lay[xind][yind]) {
cover = 0;
} else {
if (x == 0 || y == 0) {
for (int t = 0; t < 2; t++) {
if (layer < lay[xind + of2[t]][yind]) {
cover &= ob[t + 1];
}
}
} else {
for (int t = 0; t < 6; t++) {
if (layer < lay[xind + of1[t][0]][yind + of1[t][1]]) {
cover &= ob[t + 1];
}
}
}
}
c[i][j][k].clr[l] |= cover;
}
}
}
}
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]);
}
}
char lt[MAXN];
for (int x = -1; x <= 1; x++) {
scanf("%s", lt);
for (int y = -1; y <= 1; y++) {
int l = lt[y + 1] == 'R' ? 0 : (lt[y + 1] == 'G' ? 1 : (lt[y + 1] == 'B' ? 2 : 3));
if (l != 3) {
solve(x, y, l);
}
}
}
char cc[15];
int ml = 0, mw = 0;
for (int i = 0; i < 13 * n; i++) {
std::fill(ans[i], ans[i] + m * 13, 0);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < h[i][j]; k++) {
int xof = ((n - i - 1) << 2) + (k << 3), yof = (j << 3) + ((n - i - 1) << 2);
for (int pos = 0; pos < 12; pos++) {
cc[pos] = c[i][j][k].color(pos);
}
for (int p = 0; p < 13; p++) {
for (int q = 0; q < 13; q++) {
if (fra[p][q] >= 0) {
if (fra[p][q] < 12) {
ans[xof + p][yof + q] = cc[fra[p][q]];
} else {
ans[xof + p][yof + q] = fra[p][q];
}
}
}
}
ml = std::max(ml, xof + 13);
mw = std::max(mw, yof + 13);
}
}
}
for (int i = ml - 1; i >= 0; i--) {
char *cur = ans[i];
int end = 0;
for (int j = 0; j < mw; j++) {
if (cur[j]) {
end = j;
}
}
end++;
for (int j = 0; j < end; j++) {
printf("%c", cur[j] ? cur[j] : ' ');
}
printf("\n");
}
return 0;
}
好厉害啊……并没有看懂……我写的是对于每个光源，算出哪些格子有遮挡效果，然后对于这些格子中的每一个，手动算出遮挡效果，感觉非常暴力……而且右前方光源的遮挡效果非常鬼畜……当时也找不到标程，查错查了好久……
大概就是，我用坐标变换直接把坐标系转到了一个垂直于光源的方向，然后只需要判断每个立方体是不是最上面的就可以了......
跪求大佬的高亮样式qwq