Google: Grid Reachability From Start to Target With Impassable Water Cells

Quick 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.

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

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

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

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.

Grid Reachability From Start to Target With Impassable Water Cells