Grid Reachability From Start to Target With Impassable Water Cells
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given an `N x N` grid. One cell is the start `S`, one cell is the target `T`, some cells are water, and every other cell is land. Water cells cannot be entered. From a cell you may move one step up, down, left or right to a neighboring cell inside the grid, as long as that neighbor is not water.
Return whether there is a path from `S` to `T`.
Each row of the grid is a string over the characters `'S'`, `'T'`, `'.'` (land) and `'W'` (water). Cells are written as `(row, column)`, 0-indexed.
### Function Signature
```python
def can_reach(grid: list[str]) -> bool:
```
### Rules
- `S` and `T` are not water. A path may pass through any cell that is not water, and it may revisit cells.
- Diagonal moves are not allowed, and the grid does not wrap around at its edges.
- Return `True` if some sequence of moves leads from `S` to `T`, and `False` otherwise.
### Constraints
- `2 <= N <= 1000`, where `N = len(grid)` and `len(grid[i]) == N` for every row `i`
- The grid contains exactly one `'S'` and exactly one `'T'`. Every other character is `'.'` or `'W'`.
- The grid has at most 1,000,000 cells.
### Examples
**Example 1**
```text
Input: grid = [
"S...",
"WWW.",
"....",
"TWWW"
]
Output: True
```
The path runs along the top row, down the last column to row `2`, left along row `2` to column `0`, and down to `T` at `(3, 0)`.
**Example 2**
```text
Input: grid = [
"S.W.",
"WW..",
"....",
"...T"
]
Output: False
```
The only land cell next to `S` is `(0, 1)`, and the water cells `(0, 2)`, `(1, 0)` and `(1, 1)` wall both of these cells in.
Overview: Decide whether a start cell can reach a target cell in a square grid when some cells are water and moves are limited to up, down, left and right. It tests modeling a grid as a graph, choosing a traversal, and handling walled-off regions and grid edges correctly.
Read the full Google Software Engineer interview experience this question came from
You are given an `N x N` grid as a list of `N` strings. Each character is one cell: `'S'` is the start, `'T'` is the target, `'.'` is land and `'W'` is water. Water cells cannot be entered. From a cell you may move one step up, down, left or right to a neighboring cell inside the grid, as long as that neighbor is not water.
Return whether there is a path from `S` to `T`. Cells are written as `(row, column)`, 0-indexed.
### Function Signature
```python
def can_reach(grid: list[str]) -> bool:
```
### Rules
- `S` and `T` are not water. A path may pass through any cell that is not water, and it may revisit cells.
- Diagonal moves are not allowed, and the grid does not wrap around at its edges.
- Return `True` if some sequence of moves leads from `S` to `T`, and `False` otherwise. The result is a single boolean, so no value in this problem exceeds `2^31 - 1`.
### Constraints
- `2 <= N <= 1000`, where `N = len(grid)` and `len(grid[i]) == N` for every row `i`
- The grid contains exactly one `'S'` and exactly one `'T'`. Every other character is `'.'` or `'W'`.
- The grid has at most 1,000,000 cells.
### Example 1
```text
Input: grid = ['S...', 'WWW.', '....', 'TWWW']
Output: True
```
The path runs along the top row, down the last column to row `2`, left along row `2` to column `0`, and down to `T` at `(3, 0)`.
### Example 2
```text
Input: grid = ['S.W.', 'WW..', '....', '...T']
Output: False
```
The only land cell next to `S` is `(0, 1)`, and the water cells `(0, 2)`, `(1, 0)` and `(1, 1)` wall both of these cells in.
Constraints
- 2 <= N <= 1000, where N = len(grid) and len(grid[i]) == N for every row i
- The grid contains exactly one 'S' and exactly one 'T'. Every other character is '.' or 'W'.
- The grid has at most 1,000,000 cells.
Examples
Input: (['S...', 'WWW.', '....', 'TWWW'],)
Expected Output: True
Explanation: Source Example 1: right along row 0, down the last column, left along row 2, then down to T at (3, 0).
Input: (['S.W.', 'WW..', '....', '...T'],)
Expected Output: False
Explanation: Source Example 2: S and (0, 1) are walled in by water at (0, 2), (1, 0) and (1, 1).
Hints
- Every cell that is not water, including S and T, can be stepped on any number of times, so the only question is which cells can be reached from S at all.
- A neighbor must stay inside the grid: a cell in the first or last row or column has fewer than four neighbors, and two cells that touch only at a corner are not neighbors.
- The grid can hold up to 1,000,000 cells and one winding route can pass through a large share of them, so keep the work proportional to the number of cells.