761. Rat in a Maze — Path Exists

You are given an m x n grid maze where each cell is either 1 (open) or 0 (blocked). A rat starts at the top-left cell (0, 0) and wants to reach the bottom-right cell (m-1, n-1). The rat may move UP, DOWN, LEFT, or RIGHT by one cell per step, but may only travel through open cells (value 1), and may not revisit a cell within a single path. Return true if such a path exists, false otherwise. If the start or end cell is 0, return false. The input is a JSON 2D array of 0/1 values.

Input: A JSON 2D integer array with 0/1 entries.

Output: Return a boolean: true or false (lowercase).

Examples

Input: [[1,1],[1,1]]
Output: true
Explanation: Fully open maze, path exists.

Input: [[1,0],[0,1]]
Output: false
Explanation: The two open cells are not reachable from each other (only via blocked cells).

Input: [[1]]
Output: true
Explanation: Start equals end; trivial path.

Constraints

• 1 <= m, n <= 5
• maze[i][j] in {0, 1}

Asked by