A car showroom is one of the few places where cars can be found indoors. Showrooms often have many cars, even above ground level! As cars are sold and new cars are bought in to sell, the cars must be moved carefully out of the showroom.
Clearly employees only wish to move cars if they have to. So, given a map of a showroom including its walls, doors and where the cars are, and the co-ordinates of the car to move, how many cars must be moved?
Cars can be rotated on the spot, but can only be moved through a completely empty space and not diagonally. Doors are always wide enough to move a car through.
One line containing two integers $R$, $C$ ($3 \le R,C \le 400$), the size of the showroom in rows and columns.
Another $R$ lines, each containing a string of $C$ characters with the following meaning:
’#’: a wall;
’c’: a car;
’D’: a door in a wall.
The first and last lines must be walls or doors. The first and last characters in a row must be walls or doors.
The next line will contain two integers $r$ ($1 < r < R$), and $c$ ($1 < c < C$), the co-ordinates of the car to move. $1,1$ is the top-left corner.
One line containing one integer: the smallest number of cars that need to be moved (including the car we are moving) to allow our desired car to leave the building.
Sample Input 1 | Sample Output 1 |
---|---|
4 5 ##### #cDc# #c#cD ##### 3 2 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
10 10 ########## #cc#ccccc# #cc#cccccD #cccccccc# ########c# #cccccccc# ###cccccc# #c#cccccc# #cccccccc# ########## 2 2 |
11 |