首页 > 专题系列 > Java解POJ > POJ 1642 Stacking Cubes [解题报告] Java
2013
11-10

POJ 1642 Stacking Cubes [解题报告] Java

Stacking Cubes

问题描述 :

Consider the following pattern of positive integers:

3 3 1

3 1

2

Note that each row is left-justified and no longer than its preceding row. Also, the entries in each row,when read left to right, are non-increasing and the entries in each column, when read top to bottom are non-increasing. We will call such a pattern a stacking pattern (SP) because such a pattern can represent a way of stacking cubes in a corner in the following way: if you consider placing the topmost row and leftmost column against walls, then the SP gives a bird’s-eye view of how many cubes are stacked vertically. The SP above represents the following corner stacking:



We will call the wall against the topmost row the right wall , and the wall against the leftmost column the left wall. Here is another SP and the corner stacking it represents:



Note that if you rotate a corner stacking so the left wall becomes the floor and the floor becomes the right wall, you still have a corner stacking. (We will call this a left rotation.) Likewise, you would still have a corner stacking if you rotate so the right wall becomes the floor and the floor becomes the left wall. (We will call this a right rotation.) So the SP of the left and right rotations of the first SP given above are
3 2 1        3 3 2

2 1 1 2 1 1
2 1 1

You should check that both the left and right rotations of the second example SP are identical to the original SP.

输入:

This problem will consist of multiple problem instances. Each problem instance will consist of a positive integer n <= 11 indicating the number of rows in the SP that follows. (n = 0 indicates the end of input.)The rows of the SP will follow, one per line with entries separated by single spaces, delimited by a trailing 0. (The trailing 0 is, of course, not part of the input data proper and you may assume that each row given has at least one cube.) Each entry in the pattern proper will be a positive integer less than or equal to 20 and there will be no more than 20 entries in any row.

输出:

For each input SP you should produce two stacking patterns corresponding to the left rotation and the right rotation (in that order). Rows of the SP should be left-justified with entries separated by a single space. One blank line should separate the left and right rotations of the given SP and two blank lines should separate output for different problem instances.

样例输入:

3
3 3 1 0
3 1 0
2 0
6
6 5 5 4 3 3 0
6 4 3 3 1 0
6 4 3 1 1 0
4 2 2 1 0
3 1 1 0
1 1 1 0
0

样例输出:

3 2 1
2 1 1
2 1

3 3 2
2 1 1
1


6 5 5 4 3 3
6 4 3 3 1
6 4 3 1 1
4 2 2 1
3 1 1
1 1 1

6 5 5 4 3 3
6 4 3 3 1
6 4 3 1 1
4 2 2 1
3 1 1
1 1 1

解题代码:

import java.io.*;
import java.util.Scanner;
public class Main
{
  public static void main(String args[])
  {
    Scanner cin=new Scanner(System.in);
    int x[]=new int[20];
    int y[]=new int[20];
    int z[]=new int[20];
    int map[][][]=new int[20][20][20];
    int tp=0;
    int i,j,k,t,n;
    while(cin.hasNext())
    {  
      n=cin.nextInt();
      if(n==0)
        return;
      if(tp==0)
        tp=1;
      else
        System.out.println("\n");
      for(i=0;i< 20;i++)
        for(j=0;j< 20;j++)
          for(k=0;k< 20;k++)
            map[i][j][k]=0;
      for(i=0,j=0;i< n;)
      {
        t=cin.nextInt();
        if(t==0)
        {
          i++;
          j=0;
        }
        else
        {
          for(k=0;k< t;k++)
            map[i][j][k]=1;
          j++;
        }
      }

      for(i=0;i< 20;i++)
      {
        for(j=0;j< 20;j++)
        {
          t=0;
          for(k=0;k< 20;k++)
            if(map[j][k][i]==1)
              t++;
          if(t==0&&j==0)
          {
            i=20;
            break;
          }
          if(t==0)
            break;
          if(j!=0)
            System.out.print(" ");
          System.out.print(t);
        }
        if(i!=20)
          System.out.println();
      }
      System.out.println();    

      for(i=0;i< 20;i++)
      {
        for(j=0;j< 20;j++)
        {
          t=0;
          for(k=0;k< 20;k++)
            if(map[k][i][j]==1)
              t++;
          if(t==0&&j==0)
          {
            i=20;
            break;
          }
          if(t==0)
            break;
          if(j!=0)
            System.out.print(" ");
          System.out.print(t);
        }
        if(i!=20)
          System.out.println();
      }
    }
    
  }
}

  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的