408158: GYM103034 A Pacman and Power Pellet

You are playing Pacman and you want to eat the power pellet to defeat the pesky ghosts.

Pacman moves one cell to the left, right, top or bottom every second. What is the minimum time needed for him to eat the power pellet?

The first line of input contains two integers, $$$n, m$$$ ($$$1 \le n,m \le 100$$$, $$$nm \ge 2$$$). The next $$$n$$$ lines of input contains $$$m$$$ characters. Each character is one of the following: #, ., P or O. P denotes Pacman, O denotes the power pellet, . denotes an empty cell and # denotes a blocked cell.

Output the minimum number of seconds required for Pacman to eat the power pellet. If the task is impossible, output $$$-1$$$.

You get $$$100$$$ points if and only if you passed all testcases.

1 2
OP

1

3 5
#####
#O..P
###..

3

3 5
#.#.#
O#.P#
.##.#

-1