1313 . Enjoy Tetris
TopCoder
Description
Tetris battle is a popular facebook game. Now we play with the T-shaped Polyominoes.
Given a n*m grids with some obstacles in some grids, and the T-shaped ' initial position and final position, please tell me at least how many steps it should take to move the T-shaped Polynomino from the start to its ending position.
There are two different type of moves:
The first is translation.
Note that here by translation it means shift of one block into either direction of up/down/left/right. Yes, this is a gravity-less version of tetris, and you can move tetris up!!! (Brand new mode?!?!!!)
ex: 
The second is 90 degree rotation in either clockwise or counter-clockwise. Origin of rotation is always the "central block" of the T-shaped polyomino.
ex: 
A move is valid iff the position of the T-shape polyomino does not overlap with any obstacle after the move. Of ourse, the polyominal must also not move outside the grid.
Input Format
First line contains a number T, denoting the number of testcases.
Each test case start with one line containing two integers n,m denoting the height and the width of the grids. The next n lines contain the grids. In the girds, the character '#' denotes the obstacle and the character '.' denotes the empty grid. And there are four characters 'S' and four charcters 'E' denote the position of start and end.
T<=25
2<=n,m<=50
Output Format
For each testcase you have to output a line. If there are no way to move the T-shape polyominoes to the goal, print -1. Otherwise print the minimum steps you have to move.
Sample Input 1
2 4 6 .S#... .SSE.. .SEEE. ...... 4 3 #S# SSS EEE #E#
Sample Output 1
4 3
Hints
Problem Source
Migrated from old NTUJ.
dreamoon
Subtasks
| No. | Testdata Range | Score |
|---|