Rush Hour

Rush Hour is a popular puzzle game which is now available on many mobile devices. There is a board of size M x N. The board is full of cars and trucks. Each car has size 1x2 and each truck has size 1x3. Cars and trucks can be either horizontal or vertical. At each step, we can move a horizontal car or truck along its row if there is no other objects in its way. Similarly we can move a vertical car