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
math__pi:
2022-11-14 14:27:43
How can I apply bfs I am completely lost !! |
|
i_love_dariia:
2021-02-04 21:58:16
For people claiming simple BFS with FASTIO will do it. How? |
|
sofyanmahmoud:
2021-01-22 15:27:38
Wrong answer !!!
|
|
grim_firefly:
2020-09-22 20:14:29
getting TLE ?
|
|
may_007:
2020-08-18 18:26:04
AC in one go. |
|
unowen98:
2020-05-16 10:18:07
HINT : Use bitmasks to maintain the directions from which a square has been approached i.e. assign each of the 8 directions to a bit in a bitset of length of 8.Use the decimal form of this bitset to track the directions. |
|
offamitkumar:
2020-04-03 12:22:05
With scanf/printf & standard bfs algo no further optimisation needed in C++. |
|
roopammishra:
2020-03-16 16:54:40
My first 2D BFS question. :) |
|
masterchef2209:
2018-12-20 16:27:35
using fast i/o with c++ will give AC
|
|
surajkumar_cse:
2018-12-15 12:03:10
Those getting TLE . Here is a little hint.
|
Added by: | Spooky |
Date: | 2009-04-16 |
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/ |