攻克最难模拟题——立体图 tyvj P1009
时间:2010年10月25日作者:坏男孩查看次数:2,308 views评论次数:7
此题号称为史上最难模拟题之一的题目。也是NOIP2008普及组复赛的最后一题。
本题要求你有非凡的空间思维和良好的字符串处理能力,才可以攻克这个超级模拟题。首先思路其实就是:
先打算所有点全都是空格,然后模拟方格子堆在一起的图像,改用什么符号用什么符号,覆盖空格,就OK啦!说那么多没用,实际看下代码就知道了。
描述 Description
小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友们讲解立体图,请你帮他画出立体图。小渊有一块面积为m*n的矩形区域,上面有m*n个边长为1的格子,每个格子上堆了一些同样大小的吉姆(积木的长宽高都是1),小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式,并且不会做任何翻转旋转,只会严格以这一种形式摆放:
+—+
/ /|
+—+ |
| | +
| |/
+—+
每个顶点用1个加号’+’表示,长用3个”-“表示,宽用1个”/”表示,高用两个”|”表示。字符’+’ ‘-‘’/’ ‘|’的ASCII码分别为43,45,47,124。字符’.’(ASCII码46)需要作为背景输出,即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则:若两块积木左右相邻,图示为:
..+—+—+
./ / /|
+—+—+ |
| | | +
| | |/.
+—+—+..若两块积木上下相邻,图示为:
..+—+
./ /|
+—+ |
| | +
| |/|
+—+ |
| | +
| |/.
+—+..
若两块积木前后相邻,图示为:….+—+
…/ /|
..+—+ |
./ /| +
+—+ |/.
| | +..
| |/…
+—+….立体图中,定义位于第(m,1)的格子(即第m行第1列的格子)上面自底向上的第一块积木(即最下面的一块积木)的左下角顶点为整张图最左下角的点。
输入格式 Input Format
输入文件drawing.in第一行有用空格隔开的两个整数m和n,表示有m*n个格子(1<=m,n<=50)。接下来的m行,是一个m*n的矩阵,每行有n个用空格隔开的整数,其中第i行第j列上的整数表示第i行第j列的格子上摞有多少个积木(1<=每个格子上的积木数<=100)。
输出格式 Output Format
输出文件drawing.out中包含题目要求的立体图,是一个K行L列的字符矩阵,其中K和L表示最少需要K行L列才能按规定输出立体图。样例输入 Sample Input
3 4
2 2 1 2
2 2 1 1
3 2 1 2样例输出 Sample Output
……+—+—+…+—+
..+—+ / /|../ /|
./ /|-+—+ |.+—+ |
+—+ |/ /| +-| | +
| | +—+ |/+—+ |/|
| |/ /| +/ /|-+ |
+—+—+ |/+—+ |/| +
| | | +-| | + |/.
| | |/ | |/| +..
+—+—+—+—+ |/…
| | | | | +….
| | | | |/…..
+—+—+—+—+……
代码如下 (C++):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | #include<stdio.h> char map[2000][2000]; //题目中没有给规模,其实通过手算或者直接计算就可以算出规模在2000*2000之内,所以这里定义了这么大的数组 int m,n; int a[50][50]; void draw(int x,int y) { int i,j; map[x][y]='+'; map[x][y+1]='-'; map[x][y+2]='-'; map[x][y+3]='-'; map[x][y+4]='+'; map[x-1][y]=map[x-2][y]='|'; map[x-1][y+4]=map[x-2][y+4]='|'; map[x-3][y]='+'; map[x-3][y+1]='-'; map[x-3][y+2]='-'; map[x-3][y+3]='-'; map[x-3][y+4]='+'; map[x-4][y+1]='/'; map[x-4][y+5]='/'; map[x-5][y+2]='+'; map[x-5][y+3]='-'; map[x-5][y+4]='-'; map[x-5][y+5]='-'; map[x-5][y+6]='+'; map[x-1][y+5]='/'; map[x-2][y+6]='+'; map[x-3][y+6]='|'; map[x-4][y+6]='|'; for(i=x-2;i<x;i++) for(j=y+1;j<=y+3;j++) map[i][j]=' '; map[x-2][y+5]=' '; map[x-3][y+5]=' '; map[x-4][y+2]=' '; map[x-4][y+3]=' '; map[x-4][y+4]=' '; } int main() { int i,j,k; int rx=2000,ry=0; for(i=0;i<2000;i++) for(j=0;j<2000;j++) map[i][j]='.'; scanf("%d%d",&m,&n); for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]); for(i=0;i<m;i++) for(j=0;j<n;j++) for(k=1;k<=100;k++) if(a[i][j]>=k) { draw(2000-2*(m-i-2)-3*k,4*j+(m-i-1)*2); if(2000-2*(m-i-2)-3*k<rx)rx=2000-2*(m-i-2)-3*k; if(4*j+(m-i-1)*2>ry)ry=4*j+(m-i-1)*2; } for(i=rx-5;i<2000;i++) { for(j=0;j<=ry+6;j++) printf("%c",map[i][j]); printf("\n"); } return 0; } |
声明: 本文采用 BY-NC-SA 协议进行授权 | 坏男孩的博客
转载请注明转自《攻克最难模拟题——立体图 tyvj P1009》
这个题很简单啊,水题啊。。跟CTSC的模拟题真是没法比啊。。。
哥们,我需要请教如何将本地的图像读取到c++的MFC做的环境中啊
@Jessy, 这个你去问下Slyar,http://www.slyar.com
进省队了不?
模拟……
模拟题的难度有多少……
这道题难不到哪里去啊。。。。。
啊啊?神牛,赶快膜拜下。。。Orz
模拟题也有BT的。。CTSC2004的公式编辑器的等