Problem D
Autonomy Reach
Problem
A self-driving taxi operates on a city grid. Each cell is either a drivable street or an obstacle. Some cells are depots where the taxi can start, and some are pickup points where passengers wait.
From any depot, the taxi may move to adjacent drivable cells (up, down, left, right; no diagonal moves). The taxi cannot enter obstacles. Your task is to determine how many pickup points are reachable from at least one depot.
Input
The first line contains two integers $R$ and $C$ ($1 \leq R, C \leq 2\, 000, R \cdot C \leq 2\, 000\, 000$), which are the grid’s dimensions. Then follow $R$ lines, each containing a string of length $C$ composed of the characters:
-
‘.’ = drivable street
-
‘#’ = building (blocked)
-
‘W’ = water (blocked)
-
‘S’ = depot (drivable; start position)
-
‘C’ = charging station (drivable)
-
‘P’ = pickup point (drivable)
There is at least one drivable cell (not necessarily a depot).
Output
Print a single integer: the number of distinct ‘P’ cells reachable from at least one ‘S’ by moving only through drivable cells (‘.’, ‘C’, ‘P’, ‘S’).
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 S# #P |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 S..P. .###. ....P |
2 |
