#K58982. Traffic System Reachability
Traffic System Reachability
Traffic System Reachability
You are given a grid representing a city. Each cell in the grid is either a road represented by 'R' or a building represented by 'B'. You are also given a starting point in the grid and a list of one or more endpoints. Your task is to determine if there is a path from the starting point to any of the endpoints by moving only up, down, left, or right on cells marked with 'R'.
The grid is provided with n rows and m columns. The starting point and endpoints use 0-indexed coordinates.
Formally, determine if there exists a path from (sx, sy) to any endpoint (ex, ey) such that every step moves to an adjacent cell (up, down, left, or right) and every cell along the path (including the endpoints) satisfies:
If such a path exists, output YES
; otherwise, output NO
.
inputFormat
The first line contains two integers n and m — the number of rows and columns in the grid, respectively.
The next n lines each contain a string of length m consisting of characters 'R' and 'B', representing the grid.
The following line contains two integers sx and sy — the starting point coordinates (0-indexed).
The next line contains an integer k — the number of endpoints.
Each of the next k lines contains two integers, representing the coordinates of an endpoint.
outputFormat
Output a single line with YES
if the traffic can reach any of the endpoints from the starting point, or NO
otherwise.
5 5
RRRRR
RBBBR
RRRRR
RBBBB
RRRRR
0 0
2
4 4
2 2
YES