407003: GYM102672 K Escape from the Abundoned House

"The Loosers club" led by Bill tries to escape from the abandoned house where Pennywise attacked them.

The house could be describes as a table $$$n \times m$$$, each cell is either an empty space or a wall. At first, the children are in an empty cell. The exit is somewhere in a different empty cell. The children can move to the next empty cell which shares a side with their cell.

To frighten the children and prevent the escape Pennywise changes the air temperature. Each time when the children move between two squares from the same row he decreases the temperature by 1 degree and when they move between two squares from the same column he increases the temperature by 1 degree. Air temperature can equal any number including negative numbers.

The children would like that when they leave the house the temperature is as closer as possible to the initial temperature. Please, help them determine the minimal possible difference between the initial temperature and the final temperature. Please, note that air temperature within the house is not important. If needed the children can visit some cells more than once, including the starting cell and the exit cell.

The first line contains two integers $$$n$$$ and $$$m$$$ — the size of the table ($$$1 \le n, m \le 1000$$$).

The following $$$n$$$ lines contain $$$m$$$ characters  — the description of the table. The description consists of symbols ".", "#", "s" and "f".

If $$$j$$$-th symbol in the $$$i$$$-th line equals "#", then there is a wall in the cell $$$(i, j)$$$, otherwise the cell is empty.

Symbol "s" notifies the starting cell, symbol "f" notifies the exit cell.

It is guaranteed that there is exactly one symbol "s" and exactly one symbol "f".

If the children will never leave the house output -1. Otherwise, output a non-negative integer  — minimal possible difference between the initial and the final temperatures.

4 3
..f
..#
s##
...

0

In the first test case friends can first move up 2 times and then move right 2 times. Then the temperature will go up by 2 and then  — down by 2. Overall, the difference will be $$$0$$$ degrees.