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.


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.


1 <= t <= 30
2 <= n, m <= 1000


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.


3 3
3 3
3 3


hide comments
karan173: 2014-04-27 22:37:24

nice problem!

zingoba: 2013-12-25 13:21:43

The time limit is too strict for non C/C++ languages. Hate to be 'forced' to write in C++.

avinash kumar: 2013-07-14 20:49:38

I tried dfs, it gave runtime error,
with the given test cases it is running fine.
i think there is the issue of excess memory with dfs, anyone has any idea?

Last edit: 2013-07-14 20:50:49
Rishav Goyal: 2013-06-22 12:31:24

still tle

Jakub ©afin: 2012-10-26 20:24:12

Spooky: are you sure you're fine with <0.5 seconds per large test case? On SPOJ's not exactly hi-end machines?

Mukesh Yadav: 2012-09-07 17:41:21

@[Trichromatic] XilinX

I m not getting it , even after BFS optimization , pls help ??

Hemant Verma: 2011-07-28 21:33:11

Hint : Use another data structure to store direction in which you have traversed the given point

Last edit: 2011-07-28 21:33:23
Spooky: 2009-04-18 13:00:03

well... I'd say you should get rid of the second 8...

[Trichromatic] XilinX: 2009-04-18 12:25:38

Mmm. Several TLEs. Now my solution has time complexity O(8*8*n*m). Could someone tell me the algorithm with which complexity will work?

Edit: I hate problems which requires heavy constant optimization.

Last edit: 2009-04-18 13:29:39
[Trichromatic] XilinX: 2009-04-18 08:21:24

Thanks for pointing that out!

Added by:Spooky
Time limit:0.703s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Advancement Spring 2009, http://sevolymp.uuuq.com/