0

Possible Duplicate:
Programming Contest Question: Counting Polyominos

There are different types of Tetris shapes. For example in shape like letters T L I Z J O S.

I'm trying to get an algorithm that can create these blocks. I'm using C++, but pseudocode would be good enough. Any ideas how to solve it or how to describe the problem to search better for it?

Block is the smallest part of a Tetris shape. If you have 4 blocks to create a shape, then there are only 7 possible shapes:

X      X    X
X  XX  X    X   X   XX  XX 
X  XX  XX  XX  XXX XX    XX
X

Rotations doesn't count. If you have 3 blocks, then you can shape only 2 blocks:

X   X
X  XX
X

How many shapes exist when you have n blocks? And how do they look like?

Community
  • 1
  • 1
Joshua Behrens
  • 818
  • 13
  • 23
  • 4
    Generally to solve these kinds of problems, you should start with paper and pen; find your algorithm and then write up the code to do it. Don't try to write code for an algorithm you don't know yet - this process tends to end up with writing bad code and having to rewrite everything anyway. Try to solve a few cases (i.e. `n = 3, 4, 5, etc.`) and look for the common pattern. In any event, you could always brute force. – RageD Jan 07 '13 at 17:24
  • 2
    Answer is here: http://stackoverflow.com/questions/4650762/programming-contest-question-counting-polyominos – Adam Stelmaszczyk Jan 07 '13 at 17:32
  • @BoBTFish kaoD's answer helped me a lot starting at the top left makes it all simpler as he said, for me too. SO at its best, thanks. – Joshua Behrens Jan 07 '13 at 17:41
  • @AdamStelmaszczyk thanks for fixing my problems with the English language. My text was too much influenced by my mother-language. – Joshua Behrens Jan 07 '13 at 17:43
  • @RageD Well that should have been my first try. – Joshua Behrens Jan 07 '13 at 17:45

0 Answers0