## Tuesday, May 24, 2016

### Tetris Shape | LeetCode Discuss

Tetris Shape | LeetCode Discuss

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

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)
#
##
#
``````
I think the tricky is how to determine two shapes are the same with different orientation.
Not just different orientation. has to consider mirror shape as well.
``````##        ##
##  and ##  are considered the same shape``````
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.