Tetris Shape


  • 0
    N

    A tetromino is a geometric shape composed of four squares, connected orthogonally.

    0_1463399259834_upload-e95fc777-c31e-4891-8351-7c3079144151
    The 5 free tetrominoes

    Given the number of squares, n, return all shapes formed by all squares connected orthogonally.

    Examples:

    n = 1:
    1)
    #
    

    n = 2
    1)
    ##
    

    n = 3
    1)
    ###
    
    2)
    #
    ##
    

    n = 4
    
    1)
    ####
    
    2)
    ##
    ##
    
    3)
    ##
    #
    #
    
    4)
    #
    ##
     #
    
    5)
    #
    ##
    #
    

  • 0

    I think the tricky is how to determine two shapes are the same with different orientation.


  • 0

    @xidui Yes. This may be tricky but luckily this is 2D, not 3D :D

    I think a dynamic programming approach may be helpful, ie: Building the result of n from n-1.


  • 0

    @1337c0d3r yes, the same I was thinking before to switch on snake's dangerous world.


  • 0
    P

    @1337c0d3r

    Not just different orientation. has to consider mirror shape as well.

    ##        ##
     ##  and ##  are considered the same shape
    

  • 0

    @porker2008 Yes, need to consider rotation + mirror. Seems like not trivial to solve.


  • 0

    A little information in advance to help you understand the problem. Forms are called free polyominoes (free because rotation , translation and reflection doesn't matter). It is used in Tetris , but it is discovered by Solomon W. Golomb in 1953. Actually I am not aware who is the author of Tetris, but it is a brilliant application of polyominoes .
    There is no formula to generate the number, we should use induction and remove all duble forms.


  • 0

  • 0
    U

    I think just rotate shape 90 degree (3 times, 4 shapes in different orientations) and every time check if set already has this shape. you are done. If not, add it to set. This way will take care of mirror, same, all orientations.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.