Thief Path to Bank Avoiding Police Patrol
You are given a rectangular grid containing police stations, exactly one thief, and exactly one bank. Each police station patrols every cell whose Manhattan distance from that station is at most k. Determine whether the thief can reach the bank without entering any police station cell or any patrolled cell.
The thief may move one cell at a time in the four directions: up, down, left, and right. The thief can move only inside the grid.
A cell is unsafe if it contains a police station or it is within patrol range of at least one police station. The thief can start only if the thief cell is safe, and the bank can be reached only if the bank cell is safe.
For the follow-up version, each police station may have a different patrol range. Police stations are matched with their ranges by scanning the grid from top to bottom and left to right.
Methods
Can Reach Bank
boolean canReachBank(List<String> grid, int k)
- Returns
true if the thief can reach the bank without entering any unsafe cell.
- Returns
false otherwise.
- Every police station uses the same patrol distance
k.
Can Reach Bank With Ranges
boolean canReachBankWithRanges(List<String> grid, List<Integer> policeRanges)
- Returns
true if the thief can reach the bank without entering any unsafe cell.
- Returns
false otherwise.
- The value at
policeRanges.get(i) is the patrol distance of the ith police station in row-major order.
Grid Format
'T' represents the thief.'B' represents the bank.'P' represents a police station.'.' represents an empty cell.
Constraints
1 ≤ grid.size() ≤ 1,0001 ≤ grid.get(i).length() ≤ 1,000- All rows in
grid have the same length.
grid contains exactly one 'T'.grid contains exactly one 'B'.grid contains at least one 'P'.0 ≤ k ≤ 1,000,000,000policeRanges.size() is equal to the number of police stations in grid.0 ≤ policeRanges.get(i) ≤ 1,000,000,000- Each character in
grid is one of 'T', 'B', 'P', or '.'.
Deterministic Rules
- For
canReachBankWithRanges, police stations are ordered by lower row index first.
- If two police stations are in the same row, the one with the lower column index comes first.
- The answer is only
true or false, so there is no need to return the actual path.
Examples
Example 1
canReachBank(grid = List.of("T..", ".P.", "..B"), k = 1)
- Output:
false
- The center police station patrols the middle neighboring cells, so the thief cannot safely reach the bank.
Example 2
canReachBank(grid = List.of("T...", "...P", "....", "...B"), k = 1)
- Output:
true
- The thief can move around the patrolled cells and reach the bank safely.
Example 3
canReachBankWithRanges(grid = List.of("T..P", "....", "P..B"), policeRanges = List.of(1, 0))
- Output:
true
- The first police station has range
1 and the second has range 0, leaving a safe route to the bank.
Example 4
canReachBankWithRanges(grid = List.of("T.P", "...", "P.B"), policeRanges = List.of(2, 1))
- Output:
false
- The first police station has range
2, which makes both the thief cell and the bank cell unsafe.