Blockade#1741
Flatlandia is a rectangular country made up of unit squares. Flatlandia is divided into provinces (2 \leq K \leq 100). Each province is a connected set of squares, meaning every cell in the province can be reached from any other cell of the same province by moving only between cells with a common side (common vertices are not enough). There is no point in Flatlandia where four provinces meet at a single vertex (that is, four squares sharing a vertex do not belong to four different provinces).
Each province is identified by its unique symbol. The capital of Flatlandia is located in the province represented by the symbol A (the capital letter A). A province is called a border province if it contains any square on the boundary of the map. The province with the capital (symbol A) is not a border province.
The king of the neighboring kingdom of Rectilania wants to conquer Flatlandia. To do this, he plans to capture the capital of Flatlandia. However, his army is not strong enough to capture it directly. Therefore, he first wants to surround the capital province to weaken the enemy through a long-term blockade, and only then capture the capital.
To surround a province, all the provinces that border it must be captured. Two provinces are considered neighboring (bordering) if there exist two squares that share a side, with one belonging to the first province and the other to the second. To capture a province, one of two conditions must be met: the province is a border province, or it borders any province that has already been captured.
The king wants to capture as few provinces as possible to establish the blockade. It is not allowed to capture the capital province, as the army is still not strong enough.
The first line contains and (3 \leq M, N \leq 200). The following lines each contain characters, describing the map of Flatlandia. The character at the -th position of the (i+1)-th line of the input corresponds to the province to which the cell belongs. All characters have an ASCII code greater than (not a space).
Output a single number: the minimum number of provinces that must be captured to surround the capital province. If blockade is impossible, output "–1".
Example 1