Minimum Steps to Fill the Grid

You are given a grid of size (n \times m) where each cell is either occupied by a plant denoted by 'P' or is empty denoted by '.'. In each step, every plant spreads to its four adjacent cells (up, down, left, right), and the cell becomes occupied by a plant. Your task is to determine the minimum number of steps required to ensure that the entire grid is occupied by plants. If it is impossible to fully occupy the grid, return -1.

The propagation follows a breadth-first search (BFS) strategy where all current plant cells simultaneously spread to adjacent empty cells.

inputFormat

The first line contains two space-separated integers (n) and (m), the number of rows and columns of the grid respectively. The following (n) lines each consist of a string of length (m) representing the grid row. Each character is either 'P' (representing a plant) or '.' (representing an empty cell).

outputFormat

Output a single integer which is the minimum number of steps required to fully occupy the grid with plants. Print -1 if it is impossible.## sample

2 2
PP
PP

0