题解 P1058 【立体图】

明人不说暗话，~~水题~~，没有算法~~第四题居然不是dp~~这是一道超级麻烦的模拟 ~~到底是谁出的？？？~~ # 一些解释 ~~我觉得楼上大佬讲的不是很清楚，我这个蒟蒻看不懂~~ ## 为什么要从下往上，从后往前，从左往右 我们可以把打印的过程抽象到实际生活中，想想你自己用立方体来摆一个立体图形。你总不可能~~用原力~~从上往下摆吧，也不可能把前面的先摆好再弄后面的吧。同理，此题按照从下往上，从后往前的顺序模拟，就不需要考虑覆盖的问题了。而对于这道题，考虑到视角的关系我们需要从左往右模拟，这点不难理解。 ## 如何找到每一个要开始打印的下标位置 ```cpp x = maxt - 2 * (m - i); y = (4 * j + 1 + (n - i + 1) * 2) - 4; ``` 对于第b[i][j]个位置的模拟，可用以上公式来找出要开始模拟的位置 推导过程如下 ```cpp x\y0123456789A 0 ..+---+---+ 1 ./ / /| 2 +---+---+ | 3 | | | + 4 | | |/| 5 +---+---+ | 6 | | | + 7 | | |/. 8 +---+---+.. ``` 对于x，观察可得：如果从前往后数每一排的值x1是一定比后面一排的值x2大2的(x2 + 2 = x1;)我们只要从一个较大的数开始模拟，依次减2，就能求得每一排的下标。(m是一共有多少排，i从m递减，还不懂可以结合一下代码） 对于y,观察可得：每一个立方的宽都包含了+---,长为4，可以得到4*j+1。同样的从前往后每一排的值y1也一定比后一排的值y2大2的（y2 + 2 = y1）得到(n-i+1)*2，两者相加-4就最终的下标位置。 ## 如何找到图形的界 ```cpp u ..+---+---+ ./ / /| +---+---+ | | | | + l| | |/|r +---+---+ | | | | + | | |/. +---+---+.. d ``` 还是这个图，我们定义四个变量u = 1e19, d = -1, l = 1e19, r = -1; 为什么这样赋值我想你不用看下面的代码也能懂 ```cpp if(i+s < l) l = i+s; if(i+s > r) r = i+s; if(j+k > d) d = j+k; if(j+k < u) u = j+k; ``` i+s/j+k 表示模拟过程中我们访问过的下标位置，如此可以找到每一个界限的最值（不懂可以看看完整代码） # 完整代码如下 ``` #include<cstdio> #include<iostream> #include<cstring> using namespace std; int m,n,b[555][555]; char p[10000][10000]; int r=-1,l=1e18,d=-1,u=1e18; char mod[6][8]={{"..+---+"}, {"./ /|"}, {"+---+ |"}, {"| | +"}, {"| |/."}, {"+---+.."}}; /* 0123456789A 0 ..+---+---+ 1 ./ / /| 2 +---+---+ | 3 | | | + 4 | | |/| 5 +---+---+ | 6 | | | + 7 | | |/. 8 +---+---+.. */ void build(int,int,int); int main() { // freopen("drawing.in","r",stdin); // freopen("drawing.out","w",stdout); memset(p,'.',sizeof(p));//初始化 cin >> m >> n; int maxt=-1; for(int i = 1;i <= m;i++) for(int j = 1;j <= n;j++) cin>>b[i][j];//输入 for(int i = 1;i <= m;i++) for(int j = 1;j <= n;j++) { int g,h; g = (3*1000+1)-2*(m-i); h = (4*j+1+(n-i+1)*2)-4; build(g,h,b[i][j]);//模拟 } for(int i = l;i <= r;i++) { for(int j = u;j <= d;j++) cout<<p[i][j];//输出 cout<<endl; } return 0; } void build(int i,int j,int h) { for(int t = 1;t <= h;t++) { for(int s = 5;s >= 0;s--) { for(int k = 6;k >=0;k--) { if(mod[s][k]=='.') continue; p[i+s][j+k] = mod[s][k]; vis[i+s][j+k] = 1; if(i+s < l) l = i+s; if(i+s > r) r = i+s; if(j+k > d) d = j+k; if(j+k < u) u = j+k;//找最值 } } i -= 3;//从下往上每打印一层i-3向上打印下一层 } } //完美结束 ``` 综上所述，~~这道题还是很水的~~有一定思维难度的，主要是模拟顺序，找下标，找界限这三步有点麻烦。 还有一天就csp2019居然还能AK noip2008的题真爽啊哈哈 ~~管理大大给个过吧，蒟蒻写题解不容易啊~~