405635: GYM102020 B Beza-10

Many thousand years ago, stories of a man, known as Ben-10's lost brother, got spread throughout the world. Legend says that he, whose name is Beza-10, was a very peculiar guy, with jaw-dropping abilities and powers. Due to that, Ben-10 got afraid that his brother would become more famous and powerful than him, so he decided to banish Beza from the dimension we live in.

Years passed, and now Beza is planning his return, so he can finally get the revenge he wanted ever since he was banned. However, travelling on different dimensions is not as simple as he thought it would be, therefore, he needs your help.

Beza-10 is trapped on a dimension represented as a $$$N$$$x$$$M$$$ grid. Because the spell cast on him was so powerful, the grid got filled with many traps, denoted by the character #, on which he can't step on, because if he did, he would suffer tremendous pain and probably die. Therefore, he can only walk on empty spaces.

Just like Ben-10, Beza possesses a magical watch, which is capable of shapeshifting him into powerful forms. However, as he is on an unknown dimension, his watch no longer works as expected: he can only shapeshift into chess pieces, except the pawn. After shapeshifting into a chosen chess piece, he will move according to the rules of this specific piece, which are just like in normal chess:

• The queen can move in any direction she wishes (vertically, diagonally or horizontally);
• The tower can move in every direction, except diagonally;
• The king can move to any of the $$$8$$$ closest points that surround him;
• The bishop can only move diagonally;
• The knight can move to any point that, together with the knight's position, makes a $$$L$$$-shaped path, i.e. the path from one point to another will contain three steps, strictly on this sequence: one on the horizontal axis, and two on the vertical axis (or the opposite - two on the horizontal and one on the vertical);
• A movement consists only on moving from one point to another, discarding its distance. That means that going from $$$(X_1, Y_1)$$$ to $$$(X_2, Y_2)$$$ defines a single movement, no matter how far apart they are from each other. Shapeshifts don't count as a movement;
• Here, chess pieces can't move from one point to another if there is one or more traps along the path or on the arrival point. The knight, though, is an exception: his movement is, essentially, a "jump": traps on the path will be ignored. However, he cannot jump to a point if it contains a trap. Also, Beza cannot move to a point outside the grid, as he would fall into infinity and never be seen again.

Also, Beza is scared that the excessive use of his watch will break it, and, therefore, decided that he will use it at most $$$K$$$ times.

Initially, assume that Beza has the form of the king chess piece, is located on the position of the grid that contains the character 'B', and wishes to reach the escape portal, marked with a 'P' on the grid. He asks you what is the minimum number of movements he will require in order to escape, doing at most $$$K$$$ shapeshifts, or report that it is impossible.

The first line of input has three integers: $$$N$$$ and $$$M$$$ ($$$2 \le N, M \le 100$$$), the grid dimensions, and $$$K$$$ ($$$0 \le K \le 100$$$), which is the maximum amount of shapeshifts Beza is willing to do. The next $$$N$$$ lines contain $$$M$$$ characters each, which can be: a 'B', denoting the starting position of Beza-10, a 'P', the position of the escape portal, a '#', which is a trap, or a single dot $$$.$$$, which is a free space that Beza can step on.

The output consists of a single integer, which is the minimum number of movements needed to reach the portal, doing at most $$$K$$$ shapeshifts. If it is not possible to reach the portal with the given grid and conditions, print $$$"$$$-1$$$"$$$ (without quotes).

3 3 3
B..
.##
.#P

2

7 5 3
B..#.
.#..#
#...#
.....
.#.#.
#.#.#
..P..

3