1 条题解
-
0
思路与算法
按后到前、左到右、低到高绘制每个单位立方体,投影基点为(4j+2(m-1-i),2(m-1-i)+3z)。模板点号透明,内部空格遮盖背面,输出最小完整画布。
正确性说明
投影视线沿三个坐标的正方向,后到前、左到右、低到高的顺序保持可遮挡物体的先后关系。每块模板的三可见面与题定线框一致,不透明边/面覆盖背后内容、模板外点号保留旧画面,归纳得到正确遮挡。按最高顶点和最右顶点分配画布恰满足最少行列。
复杂度
O(mnH+画布面积)时间(每块42格常数),O(mn+画布面积)空间;H<=100,画布高<=401、宽<=301,含点号初始化。
易错点
画面中的空格与背景点号不同,行列位置必须精确;不能把所有模板点号也覆盖到旧图上。本题特判按完整ASCII行比较,不能忽略分行和空格。
参考代码(C++11)
#include <bits/stdc++.h> using namespace std; int main() { int m, n; cin >> m >> n; vector<vector<int>> a(m, vector<int>(n)); int H = 0, W = 4 * n + 2 * m + 1; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { cin >> a[i][j]; H = max(H, 2 * (m - 1 - i) + 3 * a[i][j] + 3); } vector<string> out(H, string(W, '.')); vector<string> p = {"..+---+", "./ /|", "+---+ |", "| | +", "| |/.", "+---+.."}; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) for (int z = 0; z < a[i][j]; z++) { int x = 4 * j + 2 * (m - 1 - i), y = 2 * (m - 1 - i) + 3 * z; for (int k = 0; k < 6; k++) for (int q = 0; q < 7; q++) if (p[k][q] != '.') out[y + 5 - k][x + q] = p[k][q]; } for (int i = H - 1; i >= 0; i--) cout << out[i] << "\n"; }
- 1