This page is still under construction.

Parts of this page are still being built. What you see may change.

No Left Turns

Interview

Time limit1sMemory limit128 MB

Summary
Find the shortest path from start to finish in a maze where each step goes straight ahead or turns right.
Level

Medium5 of 10

Topics
BFS, Shortest path, Graph
Solved
No attempts yet

Problem

  • ALL HEADS: You're a Knight of the Round Table?
  • ROBIN: I am.
  • LEFT HEAD: In that case I shall have to kill you.
  • MIDDLE HEAD: Shall I?
  • RIGHT HEAD: Oh, I don't think so.
  • MIDDLE HEAD: Well, what do I think?
  • LEFT HEAD: I think kill him.
  • RIGHT HEAD: Well let's be nice to him.
  • MIDDLE HEAD: Oh shut up.

While the heads bicker, the Knight scarpers off. Right Head has taken it upon himself to search the grounds for the knight so he, Left, and Middle can go extinguish him (and then have tea and biscuits).

Consider the 8×128 \times 12 maze below, where shaded squares are walls that can't be entered.

The shortest path between Right Head (denoted by the S, for start) and the knight (denoted by the F, for finish) is of length 3, as illustrated above. But Right Head can't turn left or make U-turns. He can only move forward and turn right. That means the shortest path Right Head can find is significantly longer, at 29.

On each move Right Head enters either the square straight ahead of him or the square immediately to his right, and he then faces the direction he moved in. Only the first move is free: he may leave the start square in any of the four compass directions. The length of a path is the number of moves it takes.

Input

The first line holds a single integer NN (N>0N > 0), the number of mazes. Each maze then begins with a line holding the number of rows rr (3<r≤203 < r \le 20), a space, and the number of columns cc (3<c≤203 < c \le 20). After this follow rr lines of cc characters, representing a map of the maze.

X marks a location that is a wall and can't be occupied, S marks the start location, F marks the knight, and a blank is a location that can be freely traveled.

Output

For each maze, print on its own line the length of the shortest path Right Head can walk between the start and finish locations.

Hint

  • Right Head is capable of moving from the start position in any of the four primary compass directions. After that, he's constrained to either step forward or right.
  • The start and end locations will never be the same.
  • The maze is always surrounded by four walls.
  • You can assume that a path Right Head is able to walk always exists between the start and final locations.

Examples1

  1. Example 1

    Input
    1 
10 14 
XXXXXXXXXXXXXX 
X          XXX
X XFXXXXX    X 
XXX   XX  XX X 
X S          X 
XX  XXXXXX X X 
X        X X X 
X X      X X X 
XXX XX       X 
XXXXXXXXXXXXXX
    Expected output
    29