← 返回 twosigma 的题目列表Sewer Connectivity / Reachability in a Grid (DFS)
类型：online_judge
You are given a 2D grid grid representing a sewer/pipeline system:
. passable cell
# wall/blocked cell
S start
T target
You may move in 4 directions (up/down/left/right), no diagonals, and cannot enter #.
Determine whether T is reachable from S. Print 1 if reachable, else 0.
Input (stdin):
First line: two integers r c
Next r lines: a string of length c describing the grid
Output (stdout):
One line: 1 or 0
Constraints:
1 <= r, c <= 2000 (use iterative DFS/BFS to avoid recursion depth issues)
Example
Input:
3 4
S..#
.#..
..T.
Output:
1
Example
Input
3 4
S..#
.#..
..T.
Output
1