攻克最难模拟题——立体图 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

标签:分类:C语言
7条评论
  1. Chiwin留言于:2011年09月10日21:14 回复

    这个题很简单啊,水题啊。。跟CTSC的模拟题真是没法比啊。。。

  2. Jessy留言于:2011年01月13日17:31 回复

    哥们,我需要请教如何将本地的图像读取到c++的MFC做的环境中啊

    • 坏男孩留言于:2011年01月28日10:18 回复

      @Jessy, 这个你去问下Slyar,http://www.slyar.com

  3. 灰天飞雁留言于:2010年11月17日11:22 回复

    进省队了不?

  4. 灰天飞雁留言于:2010年11月16日17:29 回复

    模拟……
    模拟题的难度有多少……
    这道题难不到哪里去啊。。。。。

    • 坏男孩留言于:2010年11月16日17:54 回复

      啊啊?神牛,赶快膜拜下。。。Orz

    • Chiwin留言于:2011年09月10日21:14 回复

      模拟题也有BT的。。CTSC2004的公式编辑器的等

发表评论

*

*

d9 d8 d7 d6 d56 d55 d54 d53 d52 d51 d50 d5 d49 d48 d47 d46 d45 d44 d43 d42 d41 d40 d4 d39 d38 d37 d36 d35 d34 d33 d32 d31 d30 d3 d29 d28 d27 d26 d25 d24 d23 d22 d21 d20 d2 d19 d18 d17 d16 d15 d14 d13 d12 d11 d10 d1