You are on a mission to rescue two persons from debris of a building after an earthquake.
The debris are modeled as a grid. Each cell contains a character
P with the following meaning:
. represents an free cell where you can move freely
# represents an unbreakable wall
@ represents a pile of debris
P represents a person that you need to save
You are currently outside of the building (grid). You want to clear debris
@) so that each person can reach the outside of the building with a clear path (free of debris, containing only free cells). What is the minimum number of debris you need to clear in order to achieve this?
The first line contains a two integers \(n\) and \(m\) giving the number rows and columns of grid representing the building.
The follow \(n\) lines each with a string with \(m\) characters over the alphabet
".#@P" as described above.
One line with a single integer containing the minimum number of debris cells that need to be cleared
so that both people have a clear path between their initial positions and the outside of the building.
We guarantee that it is always possible to clear debris in a way such that there exists a path from each person to exit the building.
Sample Test Cases
Sample input 1
Sample output 1
Sample input 2
Sample output 2
Sample input 3
Sample output 3
Sample input 4
Sample output 4
Max file size: 1.0 MiB
Allowed extensions: .java, .cpp, .py