shunfurh
编程介的小学生
采纳率92.7%
2017-10-13 23:02 阅读 1.5k
已采纳

Bale Figures

Description

Cows like to build shapes out of hay bales. Each new shape is constructed from N (1 <= N <= 25,000) 1 x 1 x 1 cubic bales.

Bale 1 lies on the floor. After placing it, each successive bale from 2 through N is attached to the shape by placing the new bale in the proper relative position to one of the bales already placed. For instance, imagine the following figure:
Bale 1 - on the floor
Bale 2 - RIGHT Bale 1 (to Bale 1's right)
Bale 3 - FRONT Bale 2 (in front of Bale 2)
Bale 4 - FRONT Bale 3

This results in an (inverted) L-shape:

                 +--+--+                      

            1-> /  /  /| <-2                      

               +--+--+ +

               | /  /|/                         

               ++--+ +                       

               /  /|/ <-3                     

              +--+ +                          

              |  |/ <-4                       

              +--+                            

Adding another bale:
Bale 5 - OVER Bale 1

adds height to the shape:

                 +--+                            

                /  /|                           

               +--+ +--+                      

           5-> |  |/  /| <-2                      

               +--+--+ +

           1-> | /  /|/                         

               ++--+ +                       

               /  /|/ <-3                     

              +--+ +                          

              |  |/ <-4                       

              +--+                            

But adding another directive:
Bale 6 - BACK Bale 4

results in an invalid shape, since bales 3 and 6 would overlap.

Given N bales and placements described as above, output the exposed surface area of the solid figure if the shape is valid. A face is considered exposed if it is not touched by any face of any other bale and does not touch the floor (i.e., is not the bottom of a cube on the floor). Output -1 if the shape is invalid. No bale will be placed farther than 25 bale-widths from the first bale. No bale will be placed below the floor level.

Input

  • Line 1: A single integer, N

  • Lines 2..N: These lines describe the placement of bales 2..N in the form "j X". Line 2 describes bale 2; line 3 describes bale 3; and so on. The letter "X" is one of: "L" (left), "R" (right), "F" (front), "B" (back), "O" (over), or "U" (under). The bales can be glued and require no underlying support if extended over an empty space.
    Output

  • Line 1: The exposed surface area of the resulting solid. If the solid is invalid, output "-1".
    Sample Input

5
1 R
2 F
3 F
1 O
Sample Output

18

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

相关推荐