Grid Reachability From Start to Target With Impassable Water Cells

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.