QUEEN  Wandering Queen
There is a checkmates board with n rows and m columns. Some of the cells of the board are occupied. There is a queen standing on a certain cell. It wants to move to another cell of this board. Help it do this making the least possible moves. The queen can go any number of cells in any of eight directions in a single move, but it can't pass through or stand on the occupied cells and leave the board.
Input
The first line of the input contains number t – the amount of tests. Then t test descriptions follow. The first line of each test consists of two numbers n and m separated with a space. Then n lines follow each containing m characters describing the board. Character ‘.’ means a free cell, character ‘X’ – an occupied cell, character ‘S’ – the starting cell of the queen, character ‘F’ – the cell where the queen wants to go. It is guaranteed that there will be exactly one character ‘S’ and one character ‘F’ on each board.
Constraints
1 <= t <= 30
2 <= n, m <= 1000
Output
For each test case print the minimum number of moves the queen has to do to reach the desired cell. Print ‘1’ if the queen can’t reach the cell.
Example
Input: 3 3 3 S.. ... ..F 3 3 S.. XX. F.. 3 3 S.. XXX ..F Output: 1 3 1
hide comments
masterchef2209:
20181220 16:27:35
using fast i/o with c++ will give AC


surajkumar_cse:
20181215 12:03:10
Those getting TLE . Here is a little hint.


atharva_sarage:
20180608 11:06:13
nice one 

yead_025:
20180428 09:01:47
nice problem ! 

ducky94tb:
20180115 04:15:44
Finally got accepted Last edit: 20181231 03:53:06 

vanamala:
20171210 14:11:06
@SPOJ awesome work


ashish1508:
20170708 11:16:43
getting all given test cases right ...but getting WA


holmesherlock:
20170522 21:43:00
simple bfs is not helping ,,did some optimisations ,,stiil not passing 

devbishnoi:
20170219 11:32:31
Accepted with 0.30 sec


Christoph Dürr:
20161014 23:29:34
Please Spooky, the timelimit you give is too harsh. 
Added by:  Spooky 
Date:  20090416 
Time limit:  0.703s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Advancement Spring 2009, http://sevolymp.uuuq.com/ 