Helipad Steiner Connection

After years of war, our nation celebrates a glorious victory with a public holiday and a grand victory parade led by the king. The king will travel by an environmentally friendly electric helicopter that moves in a unique way – its moves are exactly like one of the following chess pieces: Rook, Queen, Bishop, Knight or King (see details below).

The country is represented as a rectangular grid. Each cell of the grid is one of three types:

• P: the palace (there is exactly one and it already has a helipad);
• C: a city (these must have a helipad);
• F: a farm (you may choose to build a helipad here at a cost of 1 unit each).

The king insists that starting from his palace, it must be possible to reach every city by a sequence of helicopter moves; however, a helicopter can only land on cells that have a helipad. Since helipads are expensive, you are to determine the minimum number of helipads that need to be built on farms in order to achieve this connectivity (note that cities are mandated to have a helipad and the palace already has one).

Helicopter moves:

• Rook: The move is valid if two cells share the same row or the same column (and are not the same cell).
• Bishop: The move is valid if the absolute differences of the row and column coordinates are equal and nonzero.
• Queen: Any move that is valid for either a rook or a bishop.
• Knight: The move is valid if the move vector is either (1,2) or (2,1) in any direction.
• King: The move is valid if the destination is one step away in any direction (i.e. the maximum of the row difference and column difference is 1).

Your task is to compute the minimum number of helipads that need to be additionally built on farms (F) so that, when combined with the already built helipads on the palace (P) and the mandatory helipads in all cities (C), the resulting network is connected under the given move rule. If it is impossible to achieve such connectivity, output -1.

Note: A helipad built on a cell is available for bridging long‐range moves. The helicopter may fly directly between any two helipad-equipped cells if the move satisfies the given chess-piece pattern.

inputFormat

The first line of input contains two integers R and C (the number of rows and columns of the grid, respectively) and a string M indicating the helicopter's move type. M will be one of: Rook, Queen, Bishop, Knight or King.

Following this are R lines, each containing a string of length C. Each character is one of P (palace), C (city) or F (farm). It is guaranteed that there is exactly one palace cell and at least one city cell.

outputFormat

Output a single integer: the minimum number of helipads that must be built on farms to enable connectivity from the palace to every city via valid helicopter moves. If no such configuration exists, output -1.

sample

3 3 King
PFF
FCF
FFF

0