Portal

The protagonist of this task, Chell, must solve a new puzzle GLaDOS has come up with.
Chell is in a room whose layout that can be represented as a matrix of dimensions \(N\) rows
and \(M\) columns. Each field can be one of the following:
●
Obstructed field - there is a wall in it (denoted as ‘#’),
●
The field where Chell is initially (denoted as ‘C’),
●
The field where Chell must get to in order to solve the puzzle (denoted as ‘F’), or
●
An empty field (denoted as ‘.’).
Chell is carrying a so-called portal gun, a gun with which you can create portals in the walls.
In each move, she can do one of the following:
●
Move to an adjacent field using one move up, down, left or right (she cannot move to
the field with a wall in it). This move lasts one unit of time.
●
Create a portal in the wall by turning towards a wall, not necessarily an adjacent one,
in the direction up, down, left or right and shooting. The portal will be created only on
the side of the wall it was hit from. In each moment, at most two portals can be
active. If a new portal is being created in the moment when two portals are already
active, the one that was created earlier will disappear. It is not possible to create a
new portal at the position of another existing portal. This move lasts a negligible
amount of time, i.e. zero amounts of time.
●
If she’s at a field that is adjacent to a wall and there’s a portal on her side of the wall,
she can step into the portal and exit to a non-obstructed field with another portal. This
move is possible if there are two active portals and lasts one unit of time.
Chell wants to know the minimal amount of time it takes for her to solve the puzzle, i.e. to
reach the field denoted as ‘F’.
Please note: The room will always have walls on the sides, and letters ‘C’ and ‘F’ will appear
only once in the matrix.

In test cases worth 50% of total points, it will hold \(4 \le N\), \(M \le 15\).

The first line of input contains the positive integers \(N\) and \(M\) (\(4 \le N\), \(M \le 500\)), the numbers
from the task.
Each of the following \(N\) lines contains \(M\) characters that describe the layout of the room.

You must output the minimal amount of time it takes to solve the puzzle, or “nemoguce”
(without quotation marks, Croatian for impossible) if it is not possible to solve it.

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 3