408158: GYM103034 A Pacman and Power Pellet

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Pacman and Power Pellettime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

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

Scoring

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

ExamplesInput
1 2
OP
Output
1
Input
3 5
#####
#O..P
###..
Output
3
Input
3 5
#.#.#
O#.P#
.##.#
Output
-1

加入题单

上一题 下一题 算法标签: