Minimum Moves to Food

You are given an n x m maze represented as a grid with S denoting the starting position of a snake, F representing the food, # representing obstacles, and . representing open spaces. The snake can move one unit in any of the four cardinal directions (up, down, left, right) at each step. Your task is to determine the minimum number of moves required for the snake to reach the food. If the snake cannot reach the food, output -1.

The moves follow the standard Manhattan distance logic. In mathematical terms, if the snake at position (x, y) needs to reach the food at position (x_F, y_F) without obstacles, the minimum number of moves is given by:

[ \text{moves} = |x - x_F| + |y - y_F| ]

However, obstacles may force the snake to take a longer route or block the path entirely.

inputFormat

The first line contains two integers n and m representing the number of rows and columns in the maze respectively. The following n lines each contain a string of length m representing a row of the maze. The maze contains exactly one S and may or may not contain an F (food).

outputFormat

Output a single integer that is the minimum number of moves required for the snake to reach the food. If it is impossible to reach the food, output -1.

4 4
S..#
.#.#
.#.F
..##

5