Prob.4 of NOIP 2008 (Junior) *Solution*

酱油 posted @ Sun, 16 Aug 2015 17:02:50 +0800 in OI life with tags Solution , 770 readers

An Ad Hoc problem? Maybe... It was five years ago that I know the problem for the first time, but I've just solved the problem RECENTLY!

"Sky Gate":http://www.luogu.org/problem/show?pid=1058

Print a graph of cubes.
There is an area of n×m, and every point has its height a[i][j] (also the number of cubes on that point).
Every cube is just like this: 
..+---+
./   /|
+---+ |
|   | +
|   |/.
+---+..
"." means blank, 
"+" means a vertex, 
"-" means horizontal lines, 
"|" means vertical lines, 
" " means the plane of the cube
So if n=1, m=1, a[1][1]=2, you should print like this:
..+---+
./   /|
+---+ |
|   | +
|   |/|
+---+ |
|   | +
|   |/.
+---+..
If n=1, m=2, a[1][1]=a[1][2]=1, you should print like this:
..+---+---+
./   /   /|
+---+---+ | 
|   |   | +
|   |   |/.
+---+---+..
If n=2, m=1, a[1][1]=a[2][1]=1, you should print like this:
....+---+
.../   /|
..+---+ |
./   /| +
+---+ |/.
|   | +..
|   |/...
+---+....
Input:
n m
a[1][1] a[1][2] ... a[1][m]
a[2][1] a[2][2] ... a[2][m]
...
a[n][1] a[n][2] ... a[n][m]
Output:
The graph required
Sample Input:
3 4
2 2 1 2
2 2 1 1
3 2 1 2
Sample Output:
......+---+---+...+---+
..+---+  /   /|../   /|
./   /|-+---+ |.+---+ |
+---+ |/   /| +-|   | +
|   | +---+ |/+---+ |/|
|   |/   /| +/   /|-+ |
+---+---+ |/+---+ |/| +
|   |   | +-|   | + |/.
|   |   |/  |   |-| +..
+---+---+---+---+ |/...
|   |   |   |   | +....
|   |   |   |   |/.....
+---+---+---+---+......
Explanations:
Just a graph we see in 2 dimensions facing the 3-dimension, right?
For all 10 testcases: 1<=n,m<=50; 1<=a[i][j]<=100 (1<=i<=n, 1<=j<=m)

 

It's the last problem in NOIP 2008 Junior, and it can be very complexed to solve. (I've already told you in advance that I am always a WEAK DISH!) But we could think like this.

Since n, m and a[i][j] are really restricted, let's make a chart then.

So the first step is to figure out the size of the graph.

When making the chart, we could draw only one cube at a time. And we could draw at a point, and slowly go upwards on each grid, which exists in the "real world".

Start from the first line, print from left to right, and the cubes nearer to us will ignore things after them.

So the only difficulty is just about calculating the formula of printing positions...

Then we could have a try!

    #include <iostream>  
    #include <cstdio>  
    #include <cstdlib>  
    #include <cstring>  
    #include <cmath>  
    #include <algorithm>  
    #include <ctime>  
    #define DONS 1010  
    using namespace std;  
    int n,i,j,k,sizex,sizey,m,a[DONS][DONS],t[DONS],tt[DONS];  
    char graph[DONS][DONS];  
    void draw(int xx,int yy)  //print a cube while point (xx,yy) is its left vertex at the bottom
    {  
        graph[xx][yy]=graph[xx][yy+4]=graph[xx-2][yy+6]=graph[xx-3][yy]=graph[xx-3][yy+4]=graph[xx-5][yy+2]=graph[xx-5][yy+6]='+';  
        graph[xx][yy+1]=graph[xx][yy+2]=graph[xx][yy+3]=graph[xx-3][yy+1]=graph[xx-3][yy+2]=graph[xx-3][yy+3]=graph[xx-5][yy+3]=graph[xx-5][yy+4]=graph[xx-5][yy+5]='-';  
        graph[xx-1][yy]=graph[xx-1][yy+4]=graph[xx-2][yy]=graph[xx-2][yy+4]=graph[xx-3][yy+6]=graph[xx-4][yy+6]='|';  
        graph[xx-1][yy+5]=graph[xx-4][yy+5]=graph[xx-4][yy+1]='/';  
        graph[xx-1][yy+1]=graph[xx-1][yy+2]=graph[xx-1][yy+3]=graph[xx-2][yy+1]=graph[xx-2][yy+2]=graph[xx-2][yy+3]=graph[xx-4][yy+2]=graph[xx-4][yy+3]=graph[xx-4][yy+4]=graph[xx-2][yy+5]=graph[xx-3][yy+5]=' ';  
    }  
    int main()  
    {  
        scanf("%d%d",&n,&m);  
        sizey=(n<<1)+1+(m<<2);  
        for(i=1;i<=n;i++)  
        {  
            for(j=1;j<=m;j++){scanf("%d",&a[i][j]);tt[i]=max(tt[i],a[i][j]);t[i]=max(a[i][j]*3+1+(n-i+1)*2,t[i]);}  
            sizex=max(sizex,t[i]);  
        }  
        for(i=1;i<=sizex;i++)for(j=1;j<=sizey;j++)graph[i][j]='.';//initialization
        for(i=1;i<=n;i++)  
            for(j=1;j<=m;j++)  
                for(k=1;k<=a[i][j];k++)  
                draw(sizex-(n-i)*2-(k-1)*3,(n-i)*2+(j-1)*4+1);//please figure out the formula by your self  
        for(i=1;i<=sizex;i++){for(j=1;j<=sizey;j++)printf("%c",graph[i][j]);puts("");}      
        return 0;  
    }  

 

And that's it, not THAT difficult.

Of course there are more ways to solve the problem. Here I used an algorithm with time complexity O(n×m×max(a[i][j])).

 

If you have a better solution, please show your solution through comments, and I'll take it seriously.

(Comments are welcomed and it is recommended that you reply in English.)

 

 

 

 

 

 

 

 

Avatar_small
orz hhw said:
Fri, 21 Aug 2015 21:07:08 +0800

%%%It's so hard and I can't solve it.


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter