Find shortest path in a maze grid
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Maze shortest path
You are given a 2D grid `maze` of size `m x n` where:
- `0` represents an open cell
- `1` represents a wall (cannot pass)
You are also given a start cell `(sr, sc)` and a target cell `(tr, tc)`.
From any open cell, you may move **up, down, left, or right** by 1 step (no diagonals), staying within bounds.
### Task
Return the **minimum number of steps** required to reach the target from the start. If it is impossible, return `-1`.
### Input/Output
- **Input:** `maze: int[][]`, `start: int[2]`, `target: int[2]`
- **Output:** `int` (minimum steps or `-1`)
### Assumptions / Constraints
- `1 <= m, n <= 200`
- `maze[sr][sc] == 0` and `maze[tr][tc] == 0`
- The grid may be large enough that an efficient graph traversal is required.
Quick Answer: This question evaluates proficiency in graph traversal and shortest-path reasoning on grid-based data structures, testing skills in pathfinding, state-space modeling, and algorithmic complexity within the Coding & Algorithms domain.
Return the minimum number of four-directional steps from start to target in a 0/1 maze, or -1 if unreachable.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: ([[0,0,1],[0,0,0],[1,0,0]], (0,0), (2,2))
Expected Output: 4
Explanation: Reachable maze.
Input: ([[0,1],[1,0]], (0,0), (1,1))
Expected Output: -1
Explanation: Unreachable.
Input: ([[0]], (0,0), (0,0))
Expected Output: 0
Explanation: Same cell.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.